当前没有测试数据。

一、题目名称

无限冒险（Infinite Adventure）

二、题目描述

贝西（Bessie）计划在一个有$N$（$1\leq N\leq10^5$）个城市的地方进行一场无限冒险。在每个城市$i$中，有一个传送门以及一个循环时间$T_i$。所有的$T_i$都是$2$的幂次方，并且$T_1+\cdots+T_N\leq10^5$。如果你在第$t$天进入城市$i$的传送门，那么你会立即从城市$c_{i,t\bmod T_i}$的传送门出来。

贝西为她的旅行制定了$Q$（$1\leq Q\leq5\cdot10^4$）个计划，每个计划由一个三元组$(v,t,\Delta)$组成。在每个计划中，她将在第$t$天从城市$v$开始。然后她将进行$\Delta$次以下操作：她将跟随当前城市的传送门，然后等待一天。对于她的每个计划，她想知道她最终会在哪个城市。

三、输入格式（从终端/标准输入读取）

1. 第一行包含两个用空格分隔的整数：$N$（节点数量）和$Q$（查询数量）。
2. 第二行包含$N$个用空格分隔的整数：$T_1,T_2,\cdots,T_N$（$1\leq T_i$，$T_i$是$2$的幂次方，且$T_1+\cdots+T_N\leq10^5$）。
3. 对于$i = 1,2,\cdots,N$，第$i + 2$行包含$T_i$个用空格分隔的正整数，即$c_{i,0},\cdots,c_{i,T_i - 1}$（$1\leq c_{i,t}\leq N$）。
4. 对于$j = 1,2,\cdots,Q$，第$j + N + 2$行包含三个用空格分隔的正整数，$v_j,t_j,\Delta_j$（$1\leq v_j\leq N$，$1\leq t_j\leq10^{18}$，$1\leq\Delta_j\leq10^{18}$），代表第$j$个查询。

四、输出格式（打印输出到终端/标准输出）

输出$Q$行。第$j$行必须包含第$j$个查询的答案。

五、样例输入及输出

样例输入1

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

样例输出1

2
2
5
4

解释：贝西的前三次冒险过程如下：

• 在第一次冒险中，她在时间$4$从城市$2$到城市$3$（时间$5$），再到城市$4$（时间$6$），最后到城市$2$（时间$7$）。
• 在第二次冒险中，她在时间$3$从城市$3$到城市$4$（时间$4$），再到城市$2$（时间$5$），接着到城市$4$（时间$6$），然后到城市$2$（时间$7$），再到城市$4$（时间$8$），最后到城市$2$（时间$9$）。
• 在第三次冒险中，她在时间$3$从城市$5$到城市$5$（时间$4$），再到城市$5$（时间$5$）。

样例输入2

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

样例输出2

2
3
5
4
2

六、评分规则

1. 输入3：$\Delta_j\leq2\cdot10^2$。
2. 输入4 - 5：$N,\sum T_j\leq2\cdot10^3$。
3. 输入6 - 8：$N,\sum T_j\leq10^4$。
4. 输入9 - 18：无其他额外约束。

题目来源：Brandon Wang。