상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다.

모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 모니터링 하려고 한다.

월급의 변화를 모니터링하는 프로그램을 작성하시오.

모든 직원의 월급은 항상 양의 정수이고 2³¹-1 이하이다.

입력 형식

첫째 줄에 직원의 수 N과 월급 변화와 조사 쿼리의 수 M이 주어진다. (1 ≤ N, M ≤ 500,000)

다음 N개 줄의 i번째 줄에는 직원 i의 초기 월급과 상사의 번호가 주어진다. (상근이는 상사가 없기 때문에, 초기 월급만 주어진다)

다음 M개 줄에는 월급 변화와 조사 쿼리가 주어진다.

1. p a x가 주어진 경우 a의 모든 부하의 월급을 x만큼 증가시킨다. (-10,000 ≤ x ≤ 10,000)
2. u a가 주어진 경우에는 a의 월급을 출력한다.

출력 형식

입력으로 u가 주어질 때마다 해당하는 직원의 월급을 출력한다.

예제 입력 1

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

예제 출력 1

8
5

예제 입력 2

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

예제 출력 2

6
5
7

예제 입력 3

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

예제 출력 3

7
9
7
5