**Note: The memory limit for this problem is 512MB, twice the default.**
Bessie is planning an infinite adventure in a land with N (1≤N≤105) cities. In each city i, there is a portal, as well as a cycling time Ti. All Ti's are powers of 2, and T1+⋯+TN≤105. If you enter city i's portal on day t, then you instantly exit the portal in Ci,t mod Ti.
Bessie has Q(1≤Q≤5⋅104) plans for her trip, each of which consists of a tuple (v,t,Δ). In each plan, she will start in city v on day t. She will then do the following Δ times: She will follow the portal in her current city, then wait one day. For each of her plans, she wants to know what city she will end up in.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two space-separated integers: N, the number of nodes, and Q, the number of queries.
The second line contains N space-separated integers: T1, T2,…,TN
(1≤Ti, Ti is a power of 2, and T1+⋯+TN≤105).
For i=1,2,…,N, line i+2 contains Ti space-separated positive integers, namely Ci,0,…,ci,Ti−1(1≤Ci,t≤N).
For j=1,2,…,Q, line j+N+2 contains three space-separated positive integers,vj,tj,Δj(1≤vj≤N, 1≤tj≤1018, and 1≤Δj≤1018) representing the j
th query.
OUTPUT FORMAT (print output to the terminal / stdout):
Print Q lines. The jth line must contain the answer to the jth query.
SAMPLE INPUT:
5 4
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 3 6
5 3 2
5 3 7
SAMPLE OUTPUT:
2
2
5
4
Bessie's first three adventures proceed as follows:
In the first adventure, she goes from city 2 at time 4 to city 3 at time 5, to city 4 at time 6, to city 2 at time 7.
In the second adventure, she goes from city 3 at time 3 to city 4 at time 4, to city 2 at time 5, to city 4 at time 6, to city 2 at time 7, to city 4 at time 8, to city 2 at time 9.
In the third adventure, she goes from city 5 at time 3 to city 5 at time 4, to city 5 at time 5.
SAMPLE INPUT:
5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000
SAMPLE OUTPUT:
2
3
5
4
2
SCORING:
Input 3:Δj≤2⋅102.
Inputs 4-5: N,∑Tj≤2⋅103.
Inputs 6-8: N,∑Tj≤104.
Inputs 9-18: No additional constraints.
Problem credits: Brandon Wang
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
