题目描述

有 $n$ 个未知数 $x_{1\dots n}$ 和 $n$ 个等式组成的同余方程组：$x_i\equiv k_i\times x_{p_i} +b_i \text{ mod } 10007$ 。

你需要应付 $q$ 个事务，每个是两种情况之一：

• A a，询问当前 $x_a$ 的解，无解输出 -1，多解输出 -2 否则输出 $x_a$。
• C a x y z，修改一个等式，$k_a\leftarrow x,p_a\leftarrow y,b_a\leftarrow z$ 。

输入格式

第一行一个整数 $n$。
下面 $n$ 行，每行三个整数 $k_i,p_i,b_i$。
接下来一行一个整数 $q$。
下面 $q$ 行，每行一个事务，格式见题目描述。

输出格式

对每个询问，输出一行一个整数。

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

数据规模与约定

对于 $100\%$ 的数据，$k_i,b_i,x_i\in [0,10007)∩\rm{Z}$。
对于 $100\%$ 的数据，$1\le n\le 3\times 10^4，0\le q\le 10^5$，其中询问事务约占总数的 $80\%$。