Mirko는 자동차를 좋아해서 그는 그의 자동차 공장을 관리하기 시작했습니다 .

공장에는 N명의 직원이 있으며, 각 일꾼은 정확히 1명의 직속 상관을 가집니다. (단 Mirko는 최고 관리자이므로 직속 상관이 없습니다) Mirko는 1번으로 나타내고, 나머지 직원들은 2번부터 N번의 번호로 나타냅니다.

각 직원은 자신보다 낮은 직급의 회사원들, 즉 계층 구조에서 자신보다 낮은 위치에 있는 직원들의 임금을 높이거나 낮출 수 있습니다. Mirko의 역할은 이 힘의 남용을 막는 것이고, 그래서 그는 때때로 특정한 직원의 임금이 얼마인지를 알기 원합니다.

그는 당신에게 입력으로 명령들이 주어질 때 직원들의 임금 변화를 관찰할 수 있는 프로그램을 제작해달라고 부탁했습니다. (어느 상황에서나 모든 임금은 양의 정수이며 32비트 정수형으로 표현할 수 있습니다.)

입력

• 첫번째 줄에는 직원의 수를 나타내는 자연수 N(1 ≤ N ≤ 500 000)과 질의의 수 M(1 ≤ M ≤ 500 000)이 공백을 사이에 두고 주어집니다.
• 다음 N개의 줄에는 1번, 2번, ..., N번 직원들의 임금과 직속 상관의 번호가 공백을 구분으로 하여 주어집니다. 단, Mirko(1번 직원)은 직속 상관이 없으므로, 그 줄에는 그의 임금만이 주어질 것입니다.
• 다음 M개 줄에는 아래와 같은 명령들이 주어집니다:
  • p A X - A번 직원의 자신보다 낮은 직급의 직원들의 임금을 X만큼 올립니다. (-10 000 ≤ X ≤ 10 000). X < 0인 경우 임금이 내려갑니다.
  • u A - Mirko는 A번 직원의 임금을 알고 싶습니다.

출력

Every employee can raise or lower the wages of all of his subordinates (both direct subordinates and those lower in the hieararchy tree). Mirko’s role is to prevent abuse of such power, so from time to time he wants to know wage of a particular employee.

He is asking you to write a program which will help him monitor wage changes, given a sequence of commands described in the input section.

Remark: at any time, all of the wages will be positive integers and will fit in standard 32-bit integer type (int in C/C++, longint in Pascal).

입력

Next N lines contain the information about employees 1, 2, ..., N (respectively): starting wage and the identifier of his direct supervisor. Remark: Mirko has no supervisor, so his line will contain only his starting wage.

Next M lines contain one of the following:

1. p A X - employee A increases (or decreases in case of a negative X) wage of all his subordinates by the amount X (-10 000 ≤ X ≤ 10 000);
2. u A - Mirko wants to know the wage of employee A.

출력

입출력 예

input

2 3
5
3 1
p 1 5
u 2
u 1

output

8
5

input

5 5
4
2 1
6 1
7 1
3 4
u 3
p 1 -1
u 3
p 4 5
u 5

output

6
5
7

input

6 7
5
4 1
3 2
7 3
2 3
3 5
p 3 2
p 2 4
u 3
u 6
p 5 -2
u 6
u 1

output

7
9
7
5

입출력 보충

5 5
4
2 1
6 1
7 1
3 4

p 1 -1

p 4 5

출처:coci
번역:tncks0121