#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

A company has *N* employees, numbered 0 to *N*-1. The boss of the company is employee 0, while every other employee *i* has a direct superior *P _{i}*. Since employee 0 has no direct superior, P

_{0}= -1. Each employee

*i*starts with an initial salary of

*S*dollars.

_{i}
There will be a total of *Q* operations that you have to handle, each of them being one of two types:

- A
*raise*operation, where we raise the salaries of employee*x*and all of their direct and indirect subordinates by*d*dollars. - A
*query*operation, where we want to know the current salary of employee*x*.

## Input

The first line of input will contain two integers, *N* and *Q*.

The next line of input will contain *N* integers, indicating the array *P*.

The next line of input will contain *N* integers, indicating the array *S*.

The next *Q* lines of input will describe one operation each, in the following formats:

*0 x d*, indicating a*raise*operation on employee*x*(and their subordinates) by*d*dollars.*1 x*, indicating a*query*operation on employee*x*.

## Output

The output should contain one line with one integer for each *query* operation, indicating the current salary of the requested employee.

## Limits

1 ≤ N, Q ≤ 10^{6}.

0 ≤ P_{i} < i, for all 1 ≤ i < N.

0 ≤ x < N

0 ≤ d, S_{i} ≤ 10^{9}.

## Sample Input

5 5 -1 0 0 1 1 1 3 2 3 2 0 1 3 1 4 0 0 2 1 1 1 3

## Sample Output

5 8 8

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 23 | 3s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o payraise -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512