Consider a string S, consisting of lowercase letters.

You are given a list of queries, each of which belong to one of the following two types:

• Q a b: Returns the number of ways of rearranging the letters in the substring [a, b] such that for each substring X in the resulting string A, Reverse(X) is also present in A. Reverse(X) reverses the string X.
• U a b: Sorts the substring [a, b] lexicographically.

Thus, given the string S and a list of queries, print the answer for each query of type 1. Since the answer can be huge, print the result modulo 106109099.

Finally, output the string S, with the updates made, if any.

Note: Two ways of rearranging the letters are considered different if, for two resulting strings A, B you can find an index i such that A[i] != B[i].

Input

First line contains T, the number of test cases.

For each test case, first line contains S, the input string.

Next line contains N, the number of queries. Each of the next N lines contains a string of the form "X a b" where X is one of {"Q", "U"} and a and b are positive integers such that 1 ≤ a ≤ b ≤ |S|.

Output

For each test case, print X + 1 lines, where X is the number of queries of type Q.

For each query of type Q, print one number which is the answer to the query.

(X + 1)th line for each test case, should contain the updated string S.

Constraints

1 ≤ T ≤ 10

1 ≤ |S| ≤ 50000

1 ≤ N ≤ 2000

Example

Input:
2
nittirichy
3
Q 2 5
U 1 4
Q 1 5
shabba
5
Q 2 3
Q 2 6
U 1 4
Q 2 5
Q 1 6

Output:
2
2
inttirichy
0
2
0
0
abhsba