#431. Bookshop
Bookshop
Description
DreamGrid will go to the bookshop tomorrow. There are books in the bookshop in total, labeled by , connected by bidirectional roads like a tree. Because DreamGrid is very rich, he will buy the books according to the strategy below: Select two books and . Walk from to along the shortest path on the tree, and check each book one by one, including the -th book and the -th book. For each book being checked now, if DreamGrid has enough money (not less than the book price), he'll buy the book and his money will be reduced by the price of the book. In case that his money is less than the price of the book being checked now, he will skip that book. BaoBao is curious about how rich DreamGrid is. You will be given queries, in each query you will be given three integers , and . Assume DreamGrid will bring dollars before buying books, and will walk from to , you are asked to tell BaoBao the amount of money DreamGrid will have after he checking all the visited books.
Format
Input
The first line contains a single integer (), the number of test cases. For each test case:
The first line of the input contains two integers and (), denoting the number of books in the bookshop and the number of queries.
The second line contains integers (), denoting the price of each book.
Each of the next lines contains two integers and (, ), denoting a bidirectional road between and . It is guaranteed that the roads form a tree.
In the next lines, the -th line contains three integers , and (, ), describing the -th query.
It is guaranteed that the sum of all is at most , and the sum of all is at most .
Output
For each query, print a single line containing an integer, denoting the amount of money DreamGrid will have after he checking all the visited books.
Samples
1
5 5
5 2 7 4 6
1 2
1 3
2 4
2 5
4 5 10
5 4 10
4 5 12
5 3 12
3 5 11
4
2
0
4
2