A long time ago...
In a galaxy far far away...
Where nobody cared about how chocolates should be shared...
#cf_span(class=[tex-font-style-sc], body=[There was Og.])
One day, Og was very bored. He has not done anything interesting after discovering fire a few months back. And so he decided to write a program in [C+]+. (It is the predecessor of the languages C, C++, C++++, C++C+CC+++C, and so on.)
[C+]+ is very similar to C++, but it has a Python-like syntax and has infinite memory. In particular, _int_s are arbitrary precision. Arrays are zero-indexed.
Here is Og's program.
Nodes are numbered 1 to $n$. Ug, Og's brother, edited the program while Og was not looking. He inserted lines in Og's code. In particular, an _else_ clause is inserted, so the code now looks like:
Og was expecting his code to halt quickly. However, after Ug's shenanigans, it continued printing numbers. Og waited patiently. After $10^(10^(10^(100)))$ years, Og is still waiting. It has printed at least $10^(100)$ numbers at this point. Og got bored again. To pass the time, he decided to look at the $i_1$th element, $i_2$th element, ..., $i_k$th element of the list. What are the $k$ numbers that Og will see?
The first line of input contains two space-separated integers $n$ and $k$. The nodes are indexed from $1$ to $n$. The tree is rooted at node $1$.
The $i$th of the next $n$ lines describes the children of node $i$. Specifically, it contains $c_i + 1$ space-separated integers $c_i, x_1, x_2, \\dots, x_{c_i}$, where $c_i$ is the number of children of node $i$, and $(x_1, x_2, \\dots, x_{c_i})$ are the children of node $i$.
The $j$th of the next $k$ lines contains $i_k$, as described in the problem statement.
Output $k$ lines. The $j$th line must contain an integer denoting the $i_j$th element of the list.
$1 <= n <= 50$
$1 <= k <= 143$
$0 <= c_i < n$
$1 <= x_i <= n$
It is guaranteed that the input describes a tree rooted at node $1$.
*Subtask 1* (27 points): $1 <= i_j <= 10^5$
*Subtask 2* (25 points): $1 <= i_j <= 10^9$
*Subtask 3* (18 points): $1 <= i_j <= 10^(15)$
*Subtask 4* (25 points): $1 <= i_j <= 10^(18)$
*Subtask 5* (5 points): $1 <= i_j <= 10^(100)$
## Input
The first line of input contains two space-separated integers $n$ and $k$. The nodes are indexed from $1$ to $n$. The tree is rooted at node $1$. The $i$th of the next $n$ lines describes the children of node $i$. Specifically, it contains $c_i + 1$ space-separated integers $c_i, x_1, x_2, \\dots, x_{c_i}$, where $c_i$ is the number of children of node $i$, and $(x_1, x_2, \\dots, x_{c_i})$ are the children of node $i$. The $j$th of the next $k$ lines contains $i_k$, as described in the problem statement.
## Output
Output $k$ lines. The $j$th line must contain an integer denoting the $i_j$th element of the list.
[samples]
## Scoring
$1 <= n <= 50$$1 <= k <= 143$$0 <= c_i < n$$1 <= x_i <= n$It is guaranteed that the input describes a tree rooted at node $1$. *Subtask 1* (27 points): $1 <= i_j <= 10^5$*Subtask 2* (25 points): $1 <= i_j <= 10^9$*Subtask 3* (18 points): $1 <= i_j <= 10^(15)$*Subtask 4* (25 points): $1 <= i_j <= 10^(18)$*Subtask 5* (5 points): $1 <= i_j <= 10^(100)$
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of nodes in a rooted tree, with nodes labeled $ 1 $ to $ n $, rooted at node $ 1 $.
For each node $ i \in \{1, \dots, n\} $, let $ c_i \in \mathbb{Z}_{\geq 0} $ denote its number of children, and let $ \text{children}(i) = (x_{i,1}, x_{i,2}, \dots, x_{i,c_i}) $ be the ordered list of its children.
Let $ L = (v_1, v_2, v_3, \dots) $ be the infinite sequence generated by a depth-first traversal of the tree, where at each node, the algorithm:
- Prints the node label,
- Then recursively visits its children in the given order.
Let $ k \in \mathbb{Z}^+ $ be the number of queries.
Let $ I = (i_1, i_2, \dots, i_k) $ be a sequence of indices, where each $ i_j \in \mathbb{Z}^+ $, and $ 1 \leq i_j \leq 10^{100} $.
**Constraints**
1. $ 1 \leq n \leq 50 $
2. $ 1 \leq k \leq 143 $
3. $ 0 \leq c_i < n $ for all $ i \in \{1, \dots, n\} $
4. For all $ i \in \{1, \dots, n\} $, $ x_{i,\ell} \in \{1, \dots, n\} $ for all $ \ell \in \{1, \dots, c_i\} $
5. The input describes a tree rooted at node $ 1 $
**Objective**
For each query index $ i_j \in I $, compute $ L[i_j] $, the $ i_j $-th element of the infinite sequence $ L $ generated by the DFS traversal described.