406720: GYM102503 Q Og and Ug

A long time ago...

In a galaxy far far away...

Where nobody cared about how chocolates should be shared...

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, ints are arbitrary precision. Arrays are zero-indexed.

Here is Og's program.

Let L = new empty list of pairs
L.push_right( pair(root, 0) )
while L is not empty:
    (node, i) = L.pop_right()
    print(node.index)
    if i != node.children.length:
        L.push_right( pair(node, i+1) )
        L.push_right( pair(node.children[i], 0) )

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:

Let L = new empty list of pairs
L.push_right( pair(root, 0) )
while L is not empty:
    (node, i) = L.pop_right()
    print(node.index)
    if i != node.children.length:
        L.push_right( pair(node, i+1) )
        L.push_right( pair(node.children[i], 0) )
    else:
        L.push_left( pair(node, 0) )

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, \ldots, x_{c_i}$$$, where $$$c_i$$$ is the number of children of node $$$i$$$, and $$$(x_1, x_2, \ldots, 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 \le n \le 50$$$

$$$1 \le k \le 143$$$

$$$0 \le c_i < n$$$

$$$1 \le x_i \le n$$$

It is guaranteed that the input describes a tree rooted at node $$$1$$$.

Subtask 1 (27 points): $$$1 \le i_j \le 10^{5}$$$

Subtask 2 (25 points): $$$1 \le i_j \le 10^{9}$$$

Subtask 3 (18 points): $$$1 \le i_j \le 10^{15}$$$

Subtask 4 (25 points): $$$1 \le i_j \le 10^{18}$$$

Subtask 5 (5 points): $$$1 \le i_j \le 10^{100}$$$

4 7
2 2 4
1 3
0
0
6
9
69
143
214
241
420

4
2
2
3
3
3
3