Canadian Computing Olympiad: 2021 Day 1, Problem 3

There is a maze that is formed by connecting ~N~ rooms via ~N-1~ corridors. The rooms are numbered ~1~ to ~N~ and each room has the shape of a circle. The corridors have the following constraints:

• Each corridor forms a connection between two distinct rooms.
• Every pair of rooms is connected by exactly one path of connected corridors.

One difficulty in navigating through this maze is that the lights are all out, so you cannot see where you are. To help with navigation, each room contains a laser pointer that initially points to a corridor. Consider the following strategy:

• Rotate the room's laser pointer clockwise until it points to another corridor.
• Follow the room's laser pointer and traverse the corridor.
• Repeat the previous two steps indefinitely.

You created ~Q~ queries to investigate this strategy. For each query, you are given an integer ~K~ and you start at room 1. Determine the final room after traversing exactly ~K~ corridors. All laser pointers will reset to their original orientation after each query.

Input Specification

The first line contains the integers ~N~ and ~Q~ ~(2 \le N \le 800\,000, 1 \le Q \le 800\,000)~.

The next ~N~ lines describe the layout of the maze, with the ~i~th of these lines describing room ~i~. Specifically, it contains an integer ~k~, the number of corridors connecting to room ~i~, followed by ~k~ integers, ~c_1\ c_2\ \dots\ c_k~, indicating the rooms that these ~k~ corridors lead to, in clockwise order. Lastly, room ~i~'s laser pointer initially points to the corridor leading to room ~c_1~.

The final ~Q~ lines describe a query, with each line containing an integer ~K~ ~(1 \le K \le 10^{15})~.

For 4 of the 25 available marks, the ~i~th corridor forms a connection between room ~i~ and room ~i+1~.

For an additional 4 of the 25 available marks, ~N \le 2\,000~ and ~Q \le 2\,000~.

For an additional 12 of the 25 available marks, ~Q = 1~.

Output Specification

Output ~Q~ lines answering the queries in order.

Sample Input

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

Sample Output

2
1
2
4
2
3

Explanation for Sample Output

This is the initial state of the maze.

The strategy will visit these rooms in order:

$$\displaystyle 1, 2, 1, 2, 4, 2, 3, \dots$$