회사 문화 2

영선회사에는 내리 칭찬이라는 문화가 있다. 상사가 직속 부하를 칭찬하면 그 부하는 자기 직속 부하에게 같은 칭찬을 그대로 전달한다. 즉, 어떤 직원이 칭찬을 받으면 그 직원 아래에 있는 모든 직원이 같은 칭찬을 받는다.

칭찬에는 정도를 나타내는 수치가 있고, 부하가 받는 수치도 똑같다.

이번에는 내리 칭찬이 실시간으로 일어난다. 쿼리는 두 종류다.

• 1 i w: $i$번 직원이 직속 상사에게 $w$만큼 칭찬을 받는다.
• 2 i: $i$번 직원이 지금까지 받은 칭찬 수치의 합을 출력한다.

직속 상사 관계와 쿼리가 주어질 때, 2번 쿼리마다 답을 출력하시오.

첫째 줄에 직원 수 $n$과 쿼리 수 $m$이 주어진다. ($2 \le n, m \le 100000$) 직원 번호는 1번부터 $n$번까지다.

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

다음 $m$개 줄에 쿼리가 한 줄에 하나씩 주어진다. 1번 쿼리는 1 i w 형식이고 $2 \le i \le n$, $1 \le w \le 1000$이다. 2번 쿼리는 2 i 형식이고 $1 \le i \le n$이다. 사장은 상사가 없으므로 칭찬을 받지 않는다.

2번 쿼리마다 그 직원이 받은 칭찬 수치의 합을 한 줄에 하나씩 출력한다.