#P16974. [SGU426] Double cyclic

[SGU426] Double cyclic

题目描述

给定长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n。一个序列的循环移位,是把开头若干个元素按原顺序移动到末尾得到的序列。所有循环移位中字典序最小的一个称为该序列的最小循环移位。

给定模数 mm,其中 0≤ai≤m−10\le a_i\le m-1。对于每个 t=0,1,…,m−1t=0,1,\ldots,m-1,定义新序列

bi(t)=(ai+t) mod mb^{(t)}_i=(a_i+t)\bmod m。

再给定 1≤k≤n1\le k\le n。对于每个 tt,求序列 b(t)b^{(t)} 的最小循环移位中的第 kk 个元素。

输入格式

第一行三个整数 n,m,kn,m,k,满足:

  • 1≤n,m≤500001\le n,m\le50000;
  • 1≤k≤n1\le k\le n。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 0≤ai≤m−10\le a_i\le m-1。

输出格式

输出 mm 行。

第 t+1t+1 行输出 b(t)b^{(t)} 的最小循环移位中的第 kk 个元素,其中 t=0,1,…,m−1t=0,1,\ldots,m-1。

样例

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