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. N lines follow, each contains 3 integers ki, pi, bi in this order. The following Q lines are the queries formatted following description 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 1 1
A 1

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