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
hide comments
[Rampage] Blue.Mary:
2022-07-30 12:47:23
Also in input 2, the 11-th line should be "C 1 1 1 1" as @apia mentioned below.
|
|
[Rampage] Blue.Mary:
2022-07-30 10:56:05
The input sections should be
|
|
Anubhav Bindlish:
2012-12-17 16:47:06
Will values of 1<=pi<=n?? |
|
apia:
2012-07-21 05:57:50
in input 2,n=4,how can I modify p[1] to 5? |
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 |