Salary Inequity

A company has $N$ employees. Every employee except one has a direct supervisor. The employee with no direct supervisor is an indirect supervisor of every other employee in the company. Employee $X$ is a subordinate of employee $Y$ if $Y$ is the direct supervisor of $X$, or if the direct supervisor of $X$ is a subordinate of $Y$.

The HR department wants to measure salary inequity. The inequity of an employee is the largest salary among that employee and all of that employee's subordinates, minus the smallest salary among the same group.

An employee sometimes raises the salary of that employee and all of that employee's subordinates by the same amount. Process the raises and the inequity queries in the order they are given.

The first line contains the number of companies $T$. $T$ is at most 20.

Each company is given as follows. The first line contains the number of employees $N$. Employees are numbered with distinct integers from 1 to $N$. The next line contains $N-1$ integers, and the $K$th of them is the number of the direct supervisor of employee $K+1$. The next line contains $N$ integers, and the $K$th of them is the salary of employee $K$. The next line contains the number of events $Q$. Each of the following $Q$ lines holds one event. A raise starts with the letter R, followed by an employee number and the amount added to the salary of that employee and all of that employee's subordinates. An inequity query starts with the letter Q, followed by the number of the employee whose inequity you must report.

• $2 \le N \le 1\,000\,000$
• $1 \le Q \le 10\,000$

For every employee $K$, the number of the direct supervisor of $K$ is smaller than $K$. Initial salaries are between 1 and 1000. Every raise amount is between 1 and 1000.

For each inequity query, print the inequity of that employee on its own line.