K. Kadane's Algorithm?
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

José is practicing graph and tree problems on the HuronCoder platform, and he came across the following challenge.

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. The parent of each node $$$u$$$ is $$$p_u$$$, with $$$1 \le p_u \lt u$$$. Each node $$$u$$$ has an associated value $$$a_u$$$.

You need to process queries of three types:

  1. Assign $$$k$$$ to the value of node $$$u$$$: $$$a_u \leftarrow k$$$.
  2. Given $$$u, v$$$, consider the unique path between $$$u$$$ and $$$v$$$. Select a non-empty contiguous subsequence of nodes along that path such that the sum of their values is maximized, and report that sum.
  3. For every $$$i$$$ in the range $$$[l, r]$$$, update $$$p_i \leftarrow \max(1,\; p_i - k)$$$, where $$$k$$$ is given in the query.

José needs your help.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$ and $$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of nodes in the tree and the number of queries.

The second line contains $$$n-1$$$ integers $$$p_2,p_2,\dots,p_n$$$ ($$$1 \leq p_i \lt i$$$) — the parent of each node.

The third line contains $$$n$$$ integers $$$a_1,a_2\dots,a_n$$$ ($$$|a_i| \leq 10^9$$$) — the initial values of each node.

The next $$$q$$$ lines describe the queries:

  1. If the operation type is $$$1$$$, the line contains three integers $$$1$$$, $$$u$$$, and $$$x$$$ ($$$1 \leq u \leq n$$$ and $$$|x| \leq 10^9$$$).
  2. If the operation type is $$$2$$$, the line contains three integers $$$2$$$, $$$u$$$, and $$$v$$$ ($$$1\leq u, v \leq n$$$).
  3. If the operation type is $$$3$$$, the line contains four integers $$$3$$$, $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1\leq l \leq r \leq n$$$ and $$$1 \leq k \lt n$$$).
Output

For each query of type $$$2$$$, print an integer representing the answer to this query.

Example
Input
5 7
1 1 3 3
3 -5 2 -1 -3
2 4 5
3 2 5 1
2 4 5
1 2 1
2 4 5
3 4 5 2
2 4 2
Output
2 -1 1 4