시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 540 97 62 30.846%

문제

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

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

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

입력

첫째 줄에 직원의 수 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가 주어질 때마다 해당하는 직원의 월급을 출력한다.

예제 입력

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

예제 출력

7
9
7
5

힌트