Background

An interstellar war has broken out in the universe.

Problem Description

To perform instant movement in the interstellar war, we have built $n$ warp points in the occupied star regions. All warp points form a rooted tree with warp point $1$ as the root. The energy value of warp point $i$ is $a_i$.

We say that warp point $u$ can reach warp point $v$ after $x$ consecutive warps if and only if starting from warp point $u$, after walking along $x$ edges we can arrive at warp point $v$, and during the process the distance to warp point $1$ keeps strictly increasing or keeps strictly decreasing.

Now we need to perform $m$ maintenance operations of the following types:

1. Space Energy Boost: For all warp points that can be reached from warp point $u$ after $x$ consecutive warps, add $y$ to their energy values.
2. Warp Test: For all warp points that can be reached from warp point $u$ after $x$ consecutive warps, output the sum of their energy values.

Input Format

The first line contains $2$ integers $n, m$.

The second line contains $n$ integers; the $i$-th one is $a_i$.

The next $n - 1$ lines each contain $2$ integers $u, v$, representing an edge.

The next $m$ lines each start with an integer $p$, then:

• If $p=1$, input $3$ integers $u, x, y$, representing one Space Energy Boost.
• If $p=2$, input $2$ integers $u, x$, representing one Warp Test.

Output Format

Output several lines of integers, which are the results of all Warp Tests.

5 5
6 8 4 10 6 
2 1
3 2
4 1
5 4
1 1 2 7
2 4 1
2 2 0
1 2 1 4
2 1 2

19
8
28

Hint

Sample Explanation

The tree is shown in the figure.

In the first operation, the warp points that satisfy the condition are warp points $3, 5$. After the operation, $a=\{6,8,11,10,13\}$.

In the second operation, the warp points that satisfy the condition are warp points $1, 5$, and the answer is $6+13=19$.

In the third operation, the warp point that satisfies the condition is warp point $2$, and the answer is $8$.

In the fourth operation, the warp points that satisfy the condition are warp points $1, 3$. After the operation, $a=\{10,8,15,10,13\}$.

In the fifth operation, the warp points that satisfy the condition are warp points $3, 5$, and the answer is $15+13=28$.

Constraints

This problem uses bundled testdata.

• Subtask #1 ($15\text{ pts}$): $n, m \le 10^3$.
• Subtask #2 ($15\text{ pts}$): $x \le 1$.
• Subtask #3 ($25\text{ pts}$): $x \le 50$.
• Subtask #4 ($45\text{ pts}$): No special constraints.

For $100\%$ of the testdata, $1\le u\le n\le3\times10^5$, $1 \le m \le 3 \times 10^5$, $1 \le a_i, y \le 10^9$, $0 \le x \le n$, $p\in\{1,2\}$。

Translated by ChatGPT 5