## Static Tree Test

Points: 20
Time limit: 2.0s
Memory limit: 256M

Problem types

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.

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

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

6916
11862
8336
15084
25583

## Comments

There are no comments at the moment.