Bessie’s Infinite Portal Adventure

Bessie is planning an endless adventure across a continent with \(N\) cities (\(1 \le N \le 10^5\)). In each city \(i\) there is a teleporter with a cyclic schedule of period \(T_i\) (each \(T_i\) is a power of 2 and \(T_1+\cdots+T_N \le 10^5\)). If you enter city \(i\)'s teleporter on day \(t\), you are immediately transported to the teleporter in city \(c_{i,\;t \bmod T_i}\>.

Bessie has \(Q\) travel plans (\(1 \le Q \le 5\cdot10^4\)). Each plan is given by a tuple \((v, t, \Delta)\). In a plan, she starts at city \(v\) on day \(t\) and then performs the following procedure exactly \(\Delta\) times: she enters the teleporter in her current city and then waits one day for the next move. For each plan, determine in which city she ends up.

The input and output formats are described below. Note that all formulas must be typeset in \(\LaTeX\) format.

inputFormat

The input begins with an integer \(N\) representing the number of cities. The following \(N\) lines each describe a city. The \(i\)-th of these lines starts with an integer \(T_i\) (the period of the teleporter in city \(i\)), followed by \(T_i\) integers: \(c_{i,0}, c_{i,1}, \dots, c_{i,T_i-1}\), where \(c_{i,j}\) is the destination city when entering the teleporter at the appropriate time.

The next line contains an integer \(Q\), the number of travel plans. Each of the following \(Q\) lines contains three integers \(v\), \(t\), and \(\Delta\), representing a plan where Bessie starts in city \(v\) on day \(t\) and performs \(\Delta\) teleportations (each followed by a one-day wait).

Note: Cities are numbered from 1 to \(N\). It is guaranteed that each \(T_i\) is a power of 2 and that \(T_1+\cdots+T_N \le 10^5\).

outputFormat

For each travel plan, output the city in which Bessie will end up after \(\Delta\) teleportations.

Output one integer per line.

sample

3
2 2 3
1 3
2 1 1
3
1 0 1
1 1 2
2 5 3

2
1
3