Modular Congruence Equation System with Updates

We are given a system of ( n ) congruence equations over the unknowns ( x_1, x_2, \dots, x_n ) defined by [ x_i \equiv k_i \times x_{p_i} + b_i \pmod{10007}, \quad 1 \le i \le n. ] Note that each equation defines ( x_i ) in terms of ( x_{p_i} ). Since every index ( i ) has exactly one equation, the dependency graph forms a functional graph (each node has exactly one outgoing edge) and every chain eventually forms a cycle.

You need to process ( q ) operations. Each operation is one of the following:

• A a: Query the current solution for \( x_a \). If there is no valid solution then output -1; if there are infinitely many solutions then output -2; otherwise, output the unique solution for \( x_a \) modulo \( 10007 \).
• C a x y z: Update the equation at index \( a \) by setting \( k_a \gets x\), \( p_a \gets y\), and \( b_a \gets z \).

How to determine the solution:

For a query operation A a, consider the chain starting at ( a ) defined by

[ f_i(x) = k_i \times x + b_i \pmod{10007}. ]

Compose the functions along the chain until a cycle is detected. Suppose the chain from ( a ) until the first repeated index (say ( t )) transforms a variable ( x ) as

[ x_a = A_{path}, x + B_{path} \pmod{10007}, ]

and the cycle (from ( t ) back to ( t )) gives an affine transformation

[ x = A_{cycle}, x + B_{cycle} \pmod{10007}. ]

Then, the unknown ( x ) must satisfy

[ (1 - A_{cycle}), x \equiv B_{cycle} \pmod{10007}. ]

The cases are as follows:

• If \( A_{cycle} \not\equiv 1 \) (mod \( 10007 \)), then there is a unique solution \( x_{cycle}\) given by: \[ x_{cycle} \equiv B_{cycle} \times (1 - A_{cycle})^{-1} \pmod{10007}, \] and the answer for \( x_a \) is \( A_{path} \times x_{cycle} + B_{path} \) modulo \( 10007 \).
• If \( A_{cycle} \equiv 1 \) and \( B_{cycle} \not\equiv 0 \) then the cycle imposes an inconsistent condition (\( 0 \equiv B_{cycle} \) with \( B_{cycle} \neq 0\)); output -1.
• If \( A_{cycle} \equiv 1 \) and \( B_{cycle} \equiv 0 \) then every value of \( x \) is valid and there exist infinitely many solutions; output -2.

Edge case (constant transformation):

If along the chain the transformation becomes constant (i.e. the coefficient becomes 0), then a cycle starting at that point forces a fixed value. In that case, check consistency and output the unique fixed value if consistent; otherwise, output -1.

All computations are done modulo ( 10007 ).

inputFormat

The first line contains two integers ( n ) and ( q ) -- the number of equations and the number of operations, respectively.\n\nThe following ( n ) lines each contain three integers: ( k_i), ( p_i ), and ( b_i ) for ( 1 \le i \le n ), representing the equation ( x_i \equiv k_i \times x_{p_i} + b_i \pmod{10007} ).\n\nEach of the next ( q ) lines represents an operation in one of the following formats:\n

\n
• A a -- Query the current solution for ( x_a ).
\n
• C a x y z -- Update the equation at index ( a ) by setting ( k_a = x,; p_a = y,; b_a = z ).
\n

outputFormat

For each query operation (lines starting with A), print a single line containing the answer for ( x_a ) modulo ( 10007 ). Print -1 if the equation has no solution and -2 if there are infinitely many solutions.

sample

3 3
2 2 3
1 3 0
1 1 0
A 1
C 2 3 3 1
A 1

10004
YOUR_OUTPUT_HERE

</p>