## Static Tree Test

Given a unweighted tree of \(N\) nodes numbered from \(1\) to \(N\), rooted at Node \(1\), and each node \(u\) has a given initial value \(v_u\), support the following operations:

`1 u x`

: Increment the subtree of node \(u\) by the value \(x\)`2 u v x`

: Increment all nodes along the path from \(u\) to \(v\) by the value \(x\)`3 u`

: Output the maximum value of all nodes in the subtree of \(u\)`4 u v`

: Output the maximum value of all nodes along the path from \(u\) to \(v\)

You will be asked to perform these operations a total of \(Q\) times.

#### Constraints

- \(1 \leq N, Q \leq 10^5\)
- \(1 \leq v_u, x, \leq 10^4\)
- \(1 \leq u, v, \leq N\)

#### Input Specification

The first line will contain \(N\) and \(Q\).

The second line will contain \(N\) numbers: the \(u\)-th number is \(v_u\).

The next line contains \(N\) numbers: the \(u\)-th number is \(p_u\), the parent of \(u\). Since Node \(1\) is always the root, the first number of input, \(p_1\), is always \(0\), representing no parent.

The next \(Q\) lines contain operations as described above.

#### Sample Input 1

```
5 4
1 2 3 4 5
0 1 1 2 2
1 1 10
2 4 5 10
3 3
4 1 5
```

#### Sample Output 1

```
13
25
```

#### Sample Input 2

```
10 10
9384 887 2778 6916 7794 8336 5387 493 6650 1422
0 1 2 3 4 4 5 4 3 8
1 9 5212
4 3 10
3 3
4 6 8
2 9 3 9803
2 7 4 8168
4 10 3
2 5 10 4422
2 6 5 5199
3 4
```

#### Sample Output 2

```
6916
11862
8336
15084
25583
```

## Comments