6759: BZOJ2759:一个动态树好题

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

有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 范浩强

加入题单

上一题 下一题 算法标签: