시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 31 22 19 67.857%

문제

영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다.

이러한 내리 갈굼은 회사에 가장 큰 불만 사항이 되었고, 사장 영선이는 이 불만을 해소해주기 위하여, 근무시간 도중 중간 중간에 야자타임을 할 것이다.

야자타임 도중에는 부하가 상사를 갈구며, 갈굼을 당하면 그 위로 쭉 사장까지 모두 갈굼을 당한다.

갈굼의 대한 정보는 실시간으로 주어진다.

입력으로 아래와 같은 쿼리가 주어질 것이다.

  • 1 i w : i번째 직원이 직속 상사로부터 w만큼 갈굼을 당한다. 만약, 야자타임 도중이라면 i번째 직원이 직속 부하 중 한명으로부터 w만큼 갈굼을 당한다. .(1≤i≤n, 1≤w≤1,000)
  • 2 i : i번째 직원이 갈굼을 당한 정도를 확인(출력).
  • 3 : 일반 근무라면 야자타임으로, 야자타임 중이라면 일반 근무로 바꾼다.

직속 상사와 직속 부하관계에 대해 주어지고,쿼리가 주어졌을 때 2번 쿼리에 따라 출력하시오.

입력

첫째 줄에는 회사의 직원 수 n명, 최초의 갈굼 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2≤n,m≤100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 직속 부하로부터 갈굼을 당한 직원 번호 i,갈굼의 수치 w가 주어진다.(1≤i≤n, 1≤w≤1,000) 각 상황별로 부하나 상사가 없을 때는 입력으로 들어오지 않는다.

처음에는 일반 근무 상태이다.

출력

2번 쿼리가 주어질 때마다, 알맞게 출력하시오.

예제 입력 1

5 8
-1 1 2 3 4
1 2 2
3
1 3 4
3
1 4 6
2 5
2 3
2 1

예제 출력 1

8
6
4

출처

  • 잘못된 데이터를 찾은 사람: jason9319