一个动态树好题

题目描述

有N个未知数x[1..n]和N个等式组成的同余方程组：
x[i]=k[i]*x[p[i]]+b[i] mod 10007
其中，k[i],b[i],x[i]∈[0,10007)∩Z
你要应付Q个事务，每个是两种情况之一：
一.询问当前x[a]的解
A a
无解输出-1
x[a]有多解输出-2
否则输出x[a]
二.修改一个等式
C a k[a] p[a] b[a]

---

输入格式

N
下面N行，每行三个整数k[i] p[i] b[i]
Q
下面Q行，每行一个事务，格式见题目描述

---

输出格式

对每个询问，输出一行一个整数。
对100%的数据，1≤N≤30000，0≤Q≤100000，时限2秒，其中询问事务约占总数的80%

---

样例输入

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

---

提示

没有写明提示

---

题目来源

By 范浩强