Consider the congruence equation system as the following form:

x[1] = k1 x[p1] + b1 (mod 10007)
x[2] = k2 x[p2] + b2 (mod 10007)
...
x[n] = kn x[pn] + bn (mod 10007)

We will ask you to achieve some instructions as the following form:

• A i: Ask the current x[i]'s value. (or "-1" for no solution, "-2" for multiply solution.)
• C i k p b: Modify the ith congruence equation to a new one.

Input

The first two lines are N and Q.
Than following Q lines are the query above.

(.. N ≤ 30, 000, Q ≤ 100, 000 .. .)

Output

For each query, print the result.

Example

Input 1:
5
2 2 1
2 3 2
2 4 3
2 5 4
2 3 5
5
A 1
A 2
C 5 3 1 1
A 4
A 5 

Output 1:
4276
7141
4256
2126

Input 2:
4
0 1 0
1 3 0
1 4 0
1 2 0
6
A 1
A 2
A 3
A 4
C 1 1 5 1
A 1

Output 2:
0
-2
-2
-2
-1