The WLM corporation has asked for your help in creating a system to determine employee salaries. WLM has ~N~ employees with ids from ~1~ to ~N~ such that employee ~1~ is the CEO. Each employee except for the CEO has exactly one boss. We say that employee ~A~ is a superior of employee ~B~ if ~A~ is the boss of ~B~ or ~A~ is a superior of the boss of ~B~. The team of employee ~A~ is defined as the set of employees that have ~A~ as their superior and ~A~ themselves. WLM would like to be able to process the following two queries efficiently:

• c A S: change the salary of employee ~A~ to ~S~.
• q A: compute the total salary of employee ~A~'s team.

Input Specification

The first line of input contains one integer ~N~ ~(2 \le N \le 100~ ~000)~, the number of employees in the company. The next ~N~ lines each two integers ~B_i, S_i (1 \le B_i \le i, 1 \le S_i < 10~ ~000)~, the boss and salary of employee ~I~, respectively. ~B_1~ will be equal to zero as employee ~1~ is the CEO. The next line contains a single integer ~Q~ ~(1 \le Q \le 200~ ~000)~, the number of queries to process. The next ~Q~ lines each contain a single query in the format described above.

Output Specification

For each query of type q A, print the answer on a separate line.

Sample Input 1

5
0 1
1 1
1 1
2 1
2 1
5
q 1
c 4 2
q 2
c 3 5
q 1

Sample Output 1

5
4
10