Background

Warning: abusing the judging system for this problem will result in an account ban!

Problem Description

The Dark Maze is a tree structure with $n$ rooms and $n - 1$ corridors. The rooms are numbered $1, 2, \cdots, n$.

The Dark Maze is completely dark, so you cannot see where you are. To tell directions, each room has a laser pointer, which initially points to one of the corridors connected to that room. You repeatedly follow the strategy below:

• Rotate the laser pointer in the current room clockwise to the next corridor.
• Walk along the corridor pointed to by the laser pointer to the other room.

You plan to start from room $1$ and repeat this strategy $k$ times, and you want to know which room you will end up in. You think this problem is too easy, so you make $q$ queries. Each query is independent, meaning that for each query all laser pointers return to their initial states.

Input Format

The first line contains two integers $n, q$.

The next $n$ lines describe the rooms. Line $i$ describes room $i$. First, an integer $k$ indicates the number of corridors connected to room $i$. Then $k$ integers $c_1, c_2, \cdots, c_k$ are given, indicating, in clockwise order, the room number at the other end of each corridor. The laser pointer in room $i$ initially points to the corridor leading to room $c_1$.

The next $q$ lines each contain one positive integer $k$.

Output Format

For each query, output one line containing the required value.

5 6
1 2
3 3 1 4
1 2
2 5 2
1 4
1
2
3
4
5
6

2
1
2
4
2
3

Hint

Sample #1 Explanation

The initial directions of the laser pointers are shown in the figure:

Constraints

For $\frac{7}{45}$ of the testdata, room $i$ is connected to rooms $i - 1$ and $i + 1$ (if those rooms exist).

For another $\frac{14}{45}$ of the testdata, $2 \leq n \leq 2 \times 10^3$, $1 \leq q \leq 2 \times 10^3$.

For another $\frac{4}{15}$ of the testdata, $q = 1$.

For $100\%$ of the testdata, $2 \leq n \leq 8 \times 10^5$, $1 \leq q \leq 8 \times 10^5$, $1 \leq k \leq 10^{15}$. It is guaranteed that the given data forms a tree.

Source

CCO2021 D1T3

Translated by ChatGPT 5