Gifts

Fanurie wants to visit each of his N friends and leave a gift of a certain value. He drew a map in the form of an undirected tree with N vertices and found a rule by which he would visit them.

From a node X, Fanurie does the following operations:

• leave the gift ready for node X;
• go through unvisited nodes in ascending order;
• returns to the node from which he arrived in X.

Fanurie decides to always start from node 1.

In order not to upset his friends, he decided to compensate for the delay by increasing the value of the gift. Thus, for each 2 ≤ i ≤ N, v[i] is known – by how much the value of the gift received by the ith visited friend increases compared to the value of the gift received by the i – 1-th visited friend. It is considered that the first friend visited receives the value v[1].

Fanurie defines the subtree induced by a list of nodes as the set of nodes in the minimal subtree that contains each node in the list. It also defines the value of a list of nodes as the sum of the values of the gifts left in the nodes.

Fanurie is asking you to help him answer Q queries of the form S K a₁ a₂ … a_K with the following meaning:

Which is the node in the subtree induced by the K elements that added to the list of nodes would make the value of the list as close as possible to S? You can not add a node that is already present in the list. If there are several options, choose the smallest node.

Fanurie promises to give you a priceless gift if you help him.

Input Specification

The first line contains two integers N and Q. The second line has N values, the elements of v. Each of the following N – 1 lines have two integers, meaning that there is an edge between them. The following Q lines describe the questions in the form S K a₁ a₂ … a_K.

Input Limits and Constraints

• 1 ≤ N ≤ 100 000;
• 1 ≤ Q ≤ 50 000;
• 1 ≤ v[i] ≤ 1 000, 1 ≤ i ≤ N;
• 1 ≤ K ≤ 3;
• 1 ≤ S ≤ 1 000 000 000;
• it is guaranteed that there are at least K + 1 nodes in any induced subtree.

Output Specification

Print one line to the standard output with Q space-separated integers, representing the answer to each query. Do not put a space after the last number!

Sample Input

1. 9 3
2. 10 5 6 4 3 2 3 1 4
3. 1 2
4. 1 3
5. 2 4
6. 2 5
7. 4 6
8. 4 7
9. 3 8
10. 3 9
11. 73 2 5 6
12. 34 1 3
13. 1000000000 2 7 8

download as text file

Output for Sample Input

1. 2 8 9

download as text file

Explanation

In the first query the induced subtree has the following node-value pairs: {(2,15), (4,21), (5,30), (6,25), (7,28)}. Both nodes 2 and 4 lead to a list value at a distance 3 from S (which is minimum). In the second example node 8 leads to a list value equal to S.