P7830 [CCO 2021] Through Another Maze Darkly

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

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.

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$.

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

#### 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](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D1T3 Translated by ChatGPT 5