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]

Format

Input

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

Output

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

Output

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

Samples

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

Limitation

1s, 1024KiB for each test case.