【NOI六连测】[D2T3] 圈圈

题目传送门：http://pan.baidu.com/s/1pLvQmx1
离线版题目：http://paste.ubuntu.com/18302981/
数据传送门：http://pan.baidu.com/s/1dF0ovZj

这一道题，std是后缀树，然而被YYY踩了，居然一个Hash / SA就可捉QAQ
还是说正事吧。
对于每一次++,分两种情况讨论：
1）有至少一个数变成0：
对于这一种情况呢，明显，字典序最小的循环串的开头，只会在这些变成0的位置中产生
所以问题就变为：比较一些给定的字符串的大小。这个看起来也不是很能做的样子。
但如果我们只考虑两两比较，那么去掉这两个串的公共前缀，我们只需要比较一个字符就可以确定大小
所以拿SA / Hash处理出公共前缀后，比较单个字符的大小即可
2）没有数变成零：
对于这一种情况，答案不会变。水涨船高嘛！
于是这个题目就搞定啦！哎，这么简单！我这个纸张考试的时候怎么没有想到呢？QAQ
%%%YYY， Hash踩标程

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 200000+9;
const int SGZ = 51000;

int n,m,k,N,M,arr[MAXN],ord[MAXN],now,tot,ans;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline bool cmp_sort(const int a, const int b){
	return arr[a] > arr[b];
}

namespace Suffix_Array{
	#define SA Suffix_Array
	int sa[MAXN],height[MAXN],t1[MAXN],t2[MAXN],bot[MAXN];
	int *tmp,*rank,m;
	
	namespace Sparse_Table{
		#define ST Sparse_Table
		int MN[MAXN][20];
		
		inline void init(){
			for (int i=1;i<=n;i++) MN[i][0]=height[i];
			for (int k=1;k<=16;k++)	for (int i=1;i<=n;i++)
				MN[i][k] = min(MN[i][k-1],MN[i+(1<<k-1)][k-1]); } inline int query(int l, int r){ if (l > r) swap(l,r); l++;
			int k=0,len=1,L=(r-l+1);
			while (len <= L/2) len*=2,k++;
			return min(MN[l][k],MN[r-len+1][k]);
		}
	};
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) if (rank[i]>1){
			int sta = max(0,height[rank[i-1]]-1);
			int p1=i+sta, p2=sa[rank[i]-1]+sta;
			while (arr[p1++]==arr[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		tmp=t1; rank=t2; m=SGZ;
		for (int i=1;i<=m;i++) bot[i] = 0;
		for (int i=1;i<=n;i++) bot[tmp[i]=arr[i]+1]++;
		for (int i=2;i<=m;i++) bot[i] += bot[i-1];
		for (int i=n;i;i--) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++)
			rank[sa[i]] = (tmp[sa[i]]==tmp[sa[i-1]])?m:++m;
			
		for (int k=1;k<=n;k*=2){ int T=0;
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
			
			swap(tmp,rank);
			rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++) if (tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]]=m; else rank[sa[i]] = ++m; if (m >= n) break;
		}
		GetHeight();
		ST::init();
	}
	
	inline int query(int a, int b){
		return ST::query(rank[a],rank[b]);
	}
};

int main(){
	freopen("cyclic.in","r",stdin);
	freopen("cyclic.out","w",stdout);
	scanf("%d%d%d",&N,&M,&k);
	for (int i=1;i<=N;i++) ord[i]=i,
		arr[i]=arr[i+N]=read();
	n = N*2; now = M-1; tot=1; SA::build();
	sort(ord+1,ord+1+N,cmp_sort);
	
	for (int i=1;i<=n;i++) if (SA::sa[i]<=N) {ans=SA::sa[i];break;}
	printf("%d\n",arr[ans+k-1]);
	for (int i=1;i<M;i++,now--){
		if (tot <= N && arr[ord[tot]]==now){
			ans = ord[tot++];
			while (tot <= N && arr[ord[tot]]==now){ int same = SA::query(ans, ord[tot]); int t = (arr[ans+same]+i)%M-(arr[ord[tot]+same]+i)%M; if (t >= 0) ans = ord[tot]; tot++;
			} printf("%d\n",(arr[ans+k-1]+i)%M);
		} else printf("%d\n",(arr[ans+k-1]+i)%M);	
	}
	
	return 0;
}