18632번 - Goldberg Machine 다국어

Rube has constructed a brand new obscure contraption and is now testing it. The machine has n nodes numbered from 1 to n that can accomodate a marble, and n−1 tracks connecting the nodes. It is possible to get from any node to any other by following the tracks, that is, the tracks form an undirected tree.

For every node, the tracks adjacent to it are ordered: if a node v has k_v tracks adjacent to it, we will write e_v,0, . . . , e_v,kv−1 for the order in question. Further, every node has an active adjacent track selected: we will write t_v ∈ {0, . . . , k_v − 1} to denote that the track e_tv is active for the node v.

Here’s how the machine operates. First, a marble is placed at the node 1. Then, one or more steps take place. Each step proceeds as follows:

• If the marble is currently in a node v, it moves to the other endpoint of the track e_v,tv (the currently active track for the node v).
• After the ball has moved to the new node, t_v becomes equal to (t_v + 1) mod k_v (that is, the node that contained the marble at the start of the step changes its active track to the next one in the cyclic ordering of its tracks).

Rube wants you to process several queries of two kinds:

• “C v t” (1 ≤ v ≤ n, 0 ≤ t ≤ k_v − 1): set t_v = t;
• “Q x” (1 ≤ x ≤ 10¹⁸): determine the index of the node that will contain the marble after taking exactly x steps from the node 1 starting from the current configuration. Note that this query does not affect the starting configuration for any further queries.

Rube is very busy tinkering with his device, so he wants to you answer fast!

The first line contains a single integer n (2 ≤ n ≤ 10⁵): the number of nodes in the machine.

The following n lines describe the tracks. The i-th of these lines contains two integers k_i and t_i (0 ≤ t_i ≤ k_i − 1), followed by k_i distinct integers u_i,0, . . . , u_v,kv−1 (u_i,j ≠ i). This denotes:

• there are k_i tracks adjacent to the node i;
• for any j ∈ {0, . . . , k_i − 1} the track e_i,j leads from i to u_i,j;
• the track e_i,ti is currently active for the node i.

It is guaranteed that the described tracks form an undirected tree, that is:

• for any pair of distinct nodes (u, v), the node u is an endpoint of a track adjacent to v if and only if v is an endpoint of a track adjacent to u;
• there are n − 1 distinct undirected tracks, that is, Σk_i = 2(n − 1);
• it is possible to get from any node to any other by following the tracks.

The following line contains a single integer q (1 ≤ q ≤ 10⁵): the number of queries.

The following q lines describe the queries in the format described above, one per line.

Print answers for all “Q x” queries in the order asked, one per line.

Here are the paths of the marbles in the sample case:

1. 1 → 2 → 1 → 3 → 1 → 2 → 4 → 2 → 5 → 2 → 1
2. 1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 1 → 2 → 4
3. 1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 7 → 3 → 1