Airplanes

문제

A new airport has been opened in Bitlandia. It is considered to be the most advanced airport in the whole world. There is a short-distance teleportation system installed which allows the travellers to get in, get out or transfer to another plane in a blink of an eye. Moreover, this even allows the planes to not stop at the airport and the system can provide this service to a multiple planes at the same time.

However,the creators of the system have not accounted for the fact that the situation can become quite complicated if passengers have to transfer from one plane to another. Let’s say that passengers need to transfer from plane i to plane j. Since planes do not stop at the airport, the plane j cannot land (and take off again) earlier than plane i does.

If the plane i is late, then the plane j will have to wait for it before landing. This means that it can delay other flights as well in case travellers from plane j need to transfer.

In an effort to solve this problem, the government of Bitlandia has issued a law stating that all travellers from the same flight have the right to transfer to at most one other flight. Moreover, the mayor of Bitlandia has ordered to create a flight control system that would allow tracking when each plane will land (and take off again).

Create this flight control system. You will be provided with regular flight schedule and information about transfers of travellers between flights.

The system will have to answer two types of queries:

• Output the currently expected landing time of plane j.
• Accept notice that plane j will be additionally late z units of time.

입력

The first line of the input contains the number of planes N.

The second line the contains N integers 1 ≤ p₁ ≤ p₂ ≤ . . . ≤ p_N ≤ 1 000 000 000. p_i shows that according to regular schedule, the plane i has to land at the airport at the moment p_i.

Further, there are N − 1 lines showing which planes the travellers are going to transfer to.

ith of these lines contains number y_i (i < y_i) meaning that there will be passengers wishing to transfer from plane i to plane y_i.

The number of queries Q is given next. Each of the remaining Q lines contains one out of two possible queries:

• I j – output the currently expected landing time of plane j;
• P j z – the plane j will additionally be late z units of time.

출력

Output the currently expected landing time of the corresponding plane for each I query. Output the numbers on separate lines.

4
2 4 5 7
2
3
4
11
I 4
P 4 2
I 4
P 1 3
I 1
I 2
I 3
P 2 1
I 1
I 2
I 3

7
9
5
5
5
5
6
6

4
1 2 4 8
3
3
4
9
I 2
I 3
P 2 3
I 2
I 3
P 1 6
I 1
I 2
I 3

2
4
5
5
7
5
7