#1386. [USACO23OPEN] Rotate and Shift B

[USACO23OPEN] Rotate and Shift B

题目描述

注意:本题的时间限制为 4 秒,是默认时间限制的 2 倍。

为了庆祝春天的到来,Farmer John 的 NN 头奶牛发明了一种有趣的舞蹈,她们围成一个圆圈,并以一种可预测的方式重新排列自己。

具体来说,圆圈上有 NN 个位置,编号从 00 到 N−1N-1,其中位置 00 紧接着位置 N−1N-1。每个位置上有一头奶牛。奶牛的编号也从 00 到 N−1N-1。初始时,奶牛 ii 位于位置 ii。你会被告知一组 KK 个“活跃”位置 0=A1<A2<⋯<AK<N0 = A_1 < A_2 < \dots < A_K < N,这意味着这些位置上的奶牛是下一批要移动的。

在舞蹈的每一分钟,会发生两件事。首先,活跃位置上的奶牛会旋转:位置 A1A_1 的奶牛移动到位置 A2A_2,位置 A2A_2 的奶牛移动到位置 A3A_3,依此类推,位置 AKA_K 的奶牛移动到位置 A1A_1。所有这些 KK 次移动同时发生,因此在旋转完成后,所有活跃位置仍然恰好有一头奶牛。接下来,活跃位置本身会移动:A1A_1 变为 A1+1A_1 + 1,A2A_2 变为 A2+1A_2 + 1,依此类推(如果某个活跃位置 Ai=N−1A_i = N-1,则 AiA_i 会循环回到 00)。

请计算舞蹈进行 TT 分钟后奶牛的顺序。

输入格式

第一行包含三个整数 NN、KK 和 TT。

第二行包含 KK 个整数,表示初始的活跃位置 A1,A2,…,AKA_1, A_2, \dots, A_K。注意 A1=0A_1 = 0,并且这些位置是按递增顺序给出的。

输出格式

输出 TT 分钟后奶牛的顺序,从位置 00 的奶牛开始,用空格分隔。

样例

5 3 4
0 2 3
1 2 3 4 0

题目来源:洛谷 P9185