# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Birthday Present

By bappy.cse38 · Limits 1s, 512 MB

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.

## Sample

InputOutput
6 5
1 2
1 3
2 4
2 5
5 6
2 3 13 5 7 11
1 1 6 10
1 1 6 12
1 1 6 19
2 5 5
1 1 6 23

1
2
3
2


### Statistics

100% Solution Ratio

YouKnowWhoEarliest, 6M ago

YouKnowWhoFastest, 0.2s

YouKnowWhoLightest, 16 MB

YouKnowWhoShortest, 2105B