那么下面，我将对█████'s head whether it has independent consciousness进行测试。

Hello, █████'s head。

Please reply if you have seen this message.

Please reply if you have seen this message.

Please reply if you have seen this message.

Please reply if you have seen this message.

Please reply if you have seen this message.

uzjandgh aidokahquxjensgkandvxhandbgsnwbegsbsbwvhzbsbwhdhdhttp://███.███.███.███/problem/███bdhbeyzhXbakxokcngehdnDbekzjycwjwjd

Problem Description

One day, several of your heads on a certain tree wanted to play a game.

Specifically, you are given a tree with $n$ nodes. Then your heads will play $m$ games on this tree:

In one game, $k$ of your heads participate, initially located at $x_1, x_2, \cdots, x_k$. For the sake of the players' mental health, it is guaranteed that all $x_i$ are distinct.

Each head has its favorite head. Surprisingly, your $i$-th head's favorite head is exactly your $(i\bmod k)+1$-th head. At every moment, all heads move toward their favorite head at a speed of $1$ edge per unit time. Note that the movement is continuous.

Now, your $(k+1)$-th head, who is watching from the side, wants to know how the game is going. It will ask you $q$ queries. Each query gives $p, t$, and you need to tell where your $p$-th head is at time $t$ (it may be on an edge; see Output Format).

Across different games, $k$ and $q$ may differ, and games are independent of each other.

Some details about the movement:

• If a head coincides with its favorite head, you may assume it will keep following its favorite head afterwards.
• If all heads gather at a single point, then all heads stop moving.

Input Format

The first line contains two integers $n, m$, representing the size of the tree and the number of games.

The next $n-1$ lines each contain two integers $u, v$, indicating there is an edge between nodes $u$ and $v$.

Then $m$ games follow, described in order:

The first line of a game contains two positive integers $k, q$, representing the number of heads and the number of queries.

The second line contains $k$ integers $x_1, x_2, \cdots, x_k$, representing the initial positions of the heads.

The next $q$ lines each contain two integers $p, t$, describing a query.

Output Format

For each game, output $q$ lines answering the queries in order.

If a head is located at node $u$, output u u (separated by a space). If a head is located on edge $u-v$, let $u < v$, output u v (separated by a space).

Example #1

Example Input

10 2
7 6
1 4
10 7
9 2
5 7
3 7
10 9
8 6
4 10
3 2
10 2 3 
1 2
1 1
4 4
9 1 8 5 
4 1
3 2
3 3
1 999999993

Example Output

10 10
9 9
7 7
7 7
7 10 
7 10

Constraints

For all data: $2 \le n \le 2\times 10^5$, $2 \le k \le n$, $1 \le q \le 2\times 10^5$, $\sum k, \sum q \le 4\times 10^5$, $1 \le t \le 10^9$.

Scoring

subtask 1 (13 pts): $n \le 3000$, $\sum k \le 6000$. Note that there is no guarantee on $q$.

subtask 2 (8 pts): The tree shape is random. The random process is: first generate a random permutation $a_1, a_2, \cdots, a_n$, then for each $a_i$ $(2 \le i \le n)$, randomly choose one from $a_1, a_2, \cdots, a_{i-1}$ and connect it to $a_i$.

subtask 3 (14 pts): The tree is a chain. Note that it is not guaranteed that the nodes on the chain are numbered consecutively from $1$ to $n$.

subtask 4 (8 pts): $k = 3$.

subtask 5 (8 pts): $k = 4$.

subtask 6 (17 pts): $k \le 30$.

subtask 7 (16 pts): $n \le 10^5$, $\sum k \le 2\times 10^5$.

subtask 8 (16 pts): No special constraints.