A134849.轮回

题目描述

终于结束的起点
终于写下句点
终于我们告别
终于我们又回到原点

——五月天《终于结束的起点》

一个个 OIer 的竞赛生涯总是从一场 NOIp 开始，大多也在一场 NOIp 中结束，好似一次次轮回在不断上演。
如果这次 NOIp 是你的起点，那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIp 是你的终点，那么祝你的 OI 回忆宛若繁星般璀璨。
也许这是你最后一次在洛谷上打比赛，也许不是。
不过，无论如何，祝你在一周后的比赛里，好运。

当然，这道题也和轮回有关系。

——洛谷 P4994 终于结束的起点
题目背景

Steve 修建了一条长度为 $d$ 格的环形矿车轨道，位置按顺时针顺序编号为第 $0,1,2,\dots,d-1$ 格。环形铁轨上运行着一辆矿车，它遵循一个长度为 $n$ 的指令序列 $a_0,a_1,\dots,a_{n-1}$ 进行移动。

具体地，给定正整数 $m$，矿车最初在第 $0$ 格，从第 $0$ 天开始，在第 $i$ 天时，矿车会按照以下方式移动：

1. 若 $i\bmod m=0$，则将指令序列 $a$ 循环右移一次，即将序列 $a$ 从 $[a_0,a_1,\dots,a_{n-2},a_{n-1}]$ 变为 $[a_{n-1},a_0,a_1,\dots,a_{n-2}]$。
2. 矿车沿顺时针方向行驶 $a_{i\bmod n}$ 格。

请你帮 Steve 求出，在第 $t-1$ 天结束时，第 $t$ 天开始前，矿车位于哪个位置？

每个测试点包含多组测试数据。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据：

第一行包含四个正整数 $d,n,m,t$，分别表示路线的长度、指令序列的长度、循环右移的周期、操作的天数。

第二行包含 $n$ 个正整数 $a_0,a_1,\dots,a_{n-1}$，表示指令序列 $a$ 的值。

对于每组测试数据，输出一行一个整数，表示矿车最终的位置。

【样例解释】

对于第一组测试数据：

• 第 $0$ 天，指令序列先变为 $[1,2,4,3,3]$，矿车顺时针移动 $a_0=1$ 格，到达第 $1$ 格；
• 第 $1$ 天，矿车顺时针移动 $a_1=2$ 格，到达第 $3$ 格；
• 第 $2$ 天，指令序列先变为 $[3,1,2,4,3]$，矿车顺时针移动 $a_2=2$ 格，到达第 $5$ 格；
• 第 $3$ 天，矿车顺时针移动 $a_3=4$ 格，到达第 $3$ 格；
• 第 $4$ 天，指令序列先变为 $[3,3,1,2,4]$，矿车顺时针移动 $a_4=4$ 格，到达第 $1$ 格；
• 第 $5$ 天，矿车顺时针移动 $a_0=3$ 格，到达第 $4$ 格。

所以第 $5$ 天结束时矿车所在的位置是第 $4$ 格。

【数据范围】

测试点编号	特殊性质
$1-2$	$T\le 10$，$t\le 10^5$
$3-5$	$T\le 10$，$n,m\le 500$
$6$	$n=m$
$7-8$	$m=2$
$9-10$	无

对于 $100\%$ 的测试数据，保证：$1\le T\le 10^4$，$1 \le n \le 2\times10^5$，$1\le m,t\le 10^{18}$，$1\le d,a_i\le 10^9$，单个测试点中所有测试数据的 $n$ 之和不超过 $2\times10^5$。