题目描述

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

你需要进行 $q$ 次操作，每次操作为下列两种情况之一：

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

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行三个整数 $k_i,p_i,b_i$。

接下来一行一个整数 $q$。

再接下来 $q$ 行，每行一个操作，见题意所述。

输出格式

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

输入输出样例 #1

输入 #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

输出 #1

4276
7141
4256
2126

说明/提示

对于所有数据，$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$，其中询问操作占总操作数的约 $80\%$。