자동차 공장의 월급 관리

상근이는 자동차 공장에서 일하며 여러 번의 승진 끝에 사장이 되었다. 공장에는 직원이 총 N명 있고, 상근이의 번호는 1번이다. 다른 직원의 번호는 2번부터 N번까지이며, 상근이를 제외한 모든 직원은 정확히 한 명의 직속 상사를 가진다.

각 직원은 자신의 모든 부하 직원의 월급을 한꺼번에 올리거나 내릴 수 있다. 여기서 부하 직원은 직속 부하뿐 아니라 그 아래의 모든 하위 직원을 포함하며, 그 직원 자신은 포함하지 않는다.

월급 변경 명령과 조회 명령이 주어질 때, 조회할 때마다 해당 직원의 현재 월급을 출력하는 프로그램을 작성하시오.

모든 직원의 월급은 항상 양의 정수이며 2^31 - 1 이하이다.

첫째 줄에 직원 수 N과 명령 수 M이 주어진다. (1 <= N, M <= 500,000)

다음 N개의 줄에는 직원 정보가 주어진다. 그중 i번째 줄은 직원 i의 정보이다. 직원 1은 상사가 없으므로 초기 월급만 주어지고, 직원 2번부터 N번까지는 초기 월급과 직속 상사의 번호가 주어진다.

다음 M개의 줄에는 다음 두 종류 중 하나의 명령이 주어진다.

1. p a x: 직원 a의 모든 부하 직원의 월급을 x만큼 증가시킨다. (-10,000 <= x <= 10,000)
2. u a: 직원 a의 현재 월급을 출력한다.

u 명령이 주어질 때마다 해당 직원의 현재 월급을 한 줄에 하나씩 출력한다.