Today is problem setter's best friend Jenny’s birthday. Long ago, Jenny, being a very clever girl, asked the problem setter to perform some queries on a tree but he couldn’t do it. Now, he seeks your help to impress her on her birthday by answering those queries.

Recall that a tree is a connected acyclic undirected graph with $n$ nodes and $n-1$ edges. In each node there are some flowers. The two type of queries are described as:

$1$$u$$v$$x$

$2$$u$$y$

For first type, you have to calculate the minimum number of vertices needed to be visited on the path from $v$ to $u$, starting at $v$, to collect at least $x$($1 <= x <= 10^{18}$) flowers, where $v$ is a descendant of $u$. Note that you cannot visit any node that is not in the path from $v$ to $u$ and you cannot skip any node of the path from $v$ to that node you've chosen at last. If it's impossible to collect at least $x$ flowers visiting all the vertices from $v$ to $u$ then you have to print -1.

For second type, you have to add $y$(y can be negative) to the existing amount flowers in node $u$. It is guaranteed that after this operation, flowers in a node will be non-negative and sum of flowers of all node of the tree will be at most $10^{18}$.

Note that 1 is the root of the tree.

Input

The first line of the input contains two integers $n$($2<=n <= 10^{5}$) and $q$($1 <= q <= 10^{5}$) where $n$ is the number of vertices of the tree and $q$ is the number of queries you have to perform.

Each of the next $n-1$ lines contains two integers $a$($1 <= a <= n$) and $b$($1 <= b <= n$) which denote an edge between $a$ and $b$. The next line contains $n$ non-negative integers $c[1], c[2], ... , c[n]$ ($0 <= c[i] <=10^{13}$) where $c[i]$ denotes the number of flowers in $i^{th}$ node. Next $q$ lines contain queries of the format described above.

Output

For each query of the first type print minimum number of nodes you have to visit to collect at least $x$($1 <= x <= 10^{18}$) flowers. If it's impossible to collect at least $x$ flowers visiting all the vertices from $v$ to $u$ then print -1.