The country where Little H lives is a tree. A tree is a connected graph with $n$ nodes and $n-1$ edges. Each node represents a city, and a child lives in city $i$, expecting to receive $a_i$ candies for Halloween.

As the Halloween Santa, Little H plans his route. A possible route involves starting from city $u$ with $m$ candies, traveling along the unique shortest path to city $v$, and giving some candies to all children on this path (including $u$ and $v$). Note that some children might not receive any candies.

After Little H distributes the candies, every child (including those not on the path) compares the number of candies received, $a'_i$, with their expected number, $a_i$. The sadness of a child is defined as:

$$ \max\{0, a_i - a'_i\}^2 $$

Little H wants to minimize the sum of the sadness of all children.

There are $q$ events occurring in chronological order. Each event is one of the following two types:

• 1 u b: The child living at node $u$ changes their mind, changing their expected number of candies to $b$, i.e., setting $a_u = b$. Note that this process affects subsequent events.
• 2 u v m: Little H simulates a Halloween route. Please tell him the minimum possible total sadness. Note that this process does not affect subsequent events.

Input

The first line contains two positive integers $n$ and $q$, representing the number of cities and the number of events, respectively.

The next $n-1$ lines each contain two positive integers $u$ and $v$, representing an edge in the tree. It is guaranteed that no edge is given twice.

The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, representing the number of candies each child expects.

The next $q$ lines each contain an event, which is either in the form 1 u b or 2 u v m, as described above.

Output

For each event of the second type, output a single non-negative integer representing the minimum total sadness.

Examples

Input 1

3 3
1 2
1 3
1 4 3
2 2 3 5
1 3 4
2 2 3 5

Output 1

3
6

Constraints

For all data, $1 \le n, q \le 10^5$, $0 \le a_i, b \le 10^9$, $0 \le m \le 10^{14}$, $1 \le u, v \le n$.

Subtask 1 ($10\%$): $n, q \le 1000, m \le 1000$.

Subtask 2 ($15\%$): $n, q \le 1000$.

Subtask 3 ($15\%$): The tree is a chain (the degree of every node is $\le 2$).

Subtask 4 ($60\%$): No additional constraints.