P10660 BZOJ2759 A Good Dynamic Tree Problem

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$.

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.

For each query, output one integer per line.

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