Problem Description

There are $n$ unknowns $x_1,x_2,\dots,x_n$ and a system of $n$ congruence equations: $x_i\equiv k_i\times x_{p_i} + b_i \pmod {10007}$.

You need to perform $q$ operations. Each operation is one of the following two types:

• A a: Query the current solution of $x_a$. If there is no solution, output -1. If there are multiple solutions, output -2. Otherwise, output $x_a$.
• C a x y z: Modify one equation: set $k_a \gets x,p_a \gets y,b_a \gets z$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain three integers $k_i,p_i,b_i$.

The next line contains an integer $q$.

The following $q$ lines each contain one operation, as described above.

Output Format

For each query, output one integer per line.

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

4276
7141
4256
2126

Hint

For all testdata, $k_i,b_i,x_i \in [0,10007) \cap \Z$. $1\leq n\leq 3\times 10^4$, $0\leq q\leq 10^5$, and query operations make up about $80\%$ of all operations.

Translated by ChatGPT 5