회사 문화 4

영선 회사에는 내리 칭찬 문화가 있다. 상사가 직속 부하를 칭찬하면 그 부하의 부하들도 같은 크기의 칭찬을 받고, 칭찬은 말단까지 연쇄적으로 퍼진다.

사장 영선이는 근무 시간 중간중간 칭찬이 퍼지는 방향을 바꾼다. 처음 방향은 부하 방향이다.

• 부하 방향: 어떤 직원이 $w$만큼 칭찬을 받으면 그 직원과 그 직원의 모든 부하가 각각 $w$만큼 칭찬을 받는다.
• 상사 방향: 어떤 직원이 $w$만큼 칭찬을 받으면 그 직원과 그 직원의 모든 상사가 각각 $w$만큼 칭찬을 받는다.

칭찬에 대한 정보는 실시간으로 주어진다. 쿼리는 세 종류다.

• 1 i w: 칭찬 방향이 부하 방향이면 $i$번 직원이 직속 상사에게서 $w$만큼 칭찬을 받고, 상사 방향이면 $i$번 직원이 직속 부하 중 한 명에게서 $w$만큼 칭찬을 받는다. 어느 쪽이든 칭찬은 현재 방향으로 퍼진다. ($1 \le i \le n$, $1 \le w \le 1\,000$)
• 2 i: $i$번 직원이 지금까지 받은 칭찬의 총합을 출력한다.
• 3: 칭찬 방향을 반대로 바꾼다. 부하 방향이면 상사 방향이 되고, 상사 방향이면 부하 방향이 된다.

직속 상사 관계와 쿼리가 주어질 때, 2번 쿼리마다 답을 출력하는 프로그램을 작성하시오.

첫째 줄에 회사의 직원 수 $n$과 쿼리의 개수 $m$이 주어진다. 직원은 1번부터 $n$번까지 번호가 매겨져 있다. ($2 \le n, m \le 100\,000$)

둘째 줄에 1번 직원부터 $n$번 직원까지의 직속 상사 번호가 차례로 주어진다. 직속 상사의 번호는 자기 번호보다 작고, 1번 직원이 사장이다. 1번 직원은 상사가 없으므로 -1이 주어진다.

다음 $m$개 줄에 쿼리가 한 줄에 하나씩 주어진다.

2번 쿼리가 주어질 때마다 해당 직원이 받은 칭찬의 총합을 한 줄에 하나씩 출력한다.