J. Lone Trail
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
If for millennia to come, our descendants have sailed along the stars, they shall greatly exalt her name.

In case of uncovering the "fake sky" of Terra, Kristen has constructed a space station.

The space station can be represented as a tree consisting of $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. As the launching process of the space station kicked off, the energy of the station is increasing. Initially, there are $$$b_i$$$ units of energy at node $$$i$$$. At the start of each day, the energy at node $$$i$$$ will increase by $$$a_i$$$.

Pure water is essential for life. As a water elf, Muelsyse needs to transport pure water to each node in the space station.

You need to process $$$k$$$ operations, which are of two types:

  1. At the end of day $$$x$$$, the station's mode is changed. Consequently, two directly connected nodes $$$u$$$ and $$$v$$$ will be chosen. $$$a_u$$$ (i.e. daily energy increase of node $$$u$$$) will decrease by $$$w$$$, and $$$a_v$$$ (i.e. daily energy increase of node $$$v$$$) will increase by $$$w$$$. It is guaranteed that there exists an edge connecting $$$u$$$ and $$$v$$$, and $$$a_u \ge w$$$ before the operation is performed.
  2. At the day $$$x$$$, Muelsyse needs to transport pure water to each node. Specifically, Muelsyse will select a node as the source of water, denoted as $$$r$$$. It costs her $$$dis_{u} \times c_u$$$ flowing shapes to transport pure water from the source of water to node $$$u$$$, where $$$dis_{u}$$$ denotes the number of edges on the path from node $$$u$$$ to $$$r$$$, and $$$c_u$$$ denotes the energy units at node $$$u$$$. Please help her choose a suitable node as water source, so that she spends the least number of flowing shapes.

It's guaranteed that $$$x$$$ is increasing among these operations. Formally, let $$$x_i$$$ be the value of $$$x$$$ in the $$$i$$$-th operation, then $$$x_i \lt x_{i+1}$$$ holds for all $$$1\leq i\leq k-1$$$.

Input

The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n, k \le 10^5$$$), denoting the number of nodes in the space station and the number of operations.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 1000$$$), where $$$a_i$$$ denotes the daily energy units increase of node $$$i$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$0 \leq b_i \leq 1000$$$), where $$$b_i$$$ denotes the initial energy units of node $$$i$$$.

The next $$$n - 1$$$ lines, each contains two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$), denoting an edge in the tree.

Next $$$k$$$ lines contain descriptions of operations. The $$$i$$$-th operation has one of two types:

  • "$$$1\ x_i\ u_i\ v_i\ w_i$$$" ($$$1 \leq x_i \leq 10^9$$$, $$$1 \leq u_i, v_i \leq n$$$), of which meanings are described above. It is guaranteed that there exists an edge connecting $$$u$$$ and $$$v$$$, and $$$a_{u_i} \ge w_i$$$ before the operation is performed.
  • "$$$2\ x_i$$$" ($$$1 \leq x_i \leq 10^9$$$), of which meaning is described above.

It's guaranteed that $$$x$$$ is increasing among these operations.

Output

For each operation type $$$2$$$, output a single integer, denoting the minimum flowing shapes Muelsyse spends.

Example
Input
5 10
1 1 4 5 1
4 1 9 1 9
1 2
2 3
2 4
1 5
2 1
1 2 3 2 3
1 3 4 2 4
1 4 2 1 8
2 5
1 6 1 5 7
2 7
2 8
2 9
2 10
Output
44
83
116
134
146
158