DCES - Dynamic Congruence Equation System

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

Added by:xiaodao
Date:2011-09-14
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CPP
Resource:FHQ's query

hide comments
2022-07-30 12:47:23 [Rampage] Blue.Mary
Also in input 2, the 11-th line should be "C 1 1 1 1" as @apia mentioned below.

[Simes]: also corrected.

Last edit: 2022-07-31 22:00:45
2022-07-30 10:56:05 [Rampage] Blue.Mary
The input sections should be
"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."

[Simes]: corrected.

Last edit: 2022-07-30 11:15:12
2012-12-17 16:47:06 Anubhav Bindlish
Will values of 1<=pi<=n??
2012-07-21 05:57:50 apia
in input 2,n=4,how can I modify p[1] to 5?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.