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 nodes and edges. In each node there are some flowers. The two type of queries are described as:
For first type, you have to calculate the minimum number of vertices needed to be visited on the path from to , starting at , to collect at least () flowers, where is a descendant of . Note that you cannot visit any node that is not in the path from to and you cannot skip any node of the path from to that node you've chosen at last. If it's impossible to collect at least flowers visiting all the vertices from to then you have to print -1.
For second type, you have to add (y can be negative) to the existing amount flowers in node . 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 .
Note that 1 is the root of the tree.
The first line of the input contains two integers () and () where is the number of vertices of the tree and is the number of queries you have to perform.
Each of the next lines contains two integers () and () which denote an edge between and . The next line contains non-negative integers () where denotes the number of flowers in node. Next lines contain queries of the format described above.
For each query of the first type print minimum number of nodes you have to visit to collect at least () flowers. If it's impossible to collect at least flowers visiting all the vertices from to then print -1.
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