Zero and One are good friends who always have fun with each other.
This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give One an tree and every node in this tree has a value. Then, Zero will ask One a series of queries. Each query contains three parameters: , , which mean that he want to know the maximum value produced by each value on the path from node to node (include node , node ). Unfortunately, One has no idea in this question. So he need you to solve it.
There are several test cases and the cases end with . For each case:
The first line contains two integers and , which are the amount of tree’s nodes and queries, respectively.
The second line contains integers and is the value on the node.
The next lines contains two integers , which means there is an connection between and .
The next m lines contains three integers , which are the parameters of Zero’s query.