Source : 中山纪念中学宋新波
Description

被污染的灰灰草原上有羊和狼。有N只动物围成一圈,每只动物是羊或狼。 该游戏从其中的一只动物开始,报出[1,K]区间的整数,若上一只动物报出的数是x,下一只动物可以报[x+1,x+K]区间的整数,游戏按顺时针方向进行。每只动物报的数字都不能超过M。若一只动物报了M这个数,它所在的种族就输了。问以第i只动物为游戏的开始,最后哪种动物会赢?

Input

第一行输入三个正整数N,M,K。

接下来一行N个正整数,分别表示N只动物的种类,以顺时针的方向给出。0代表羊,1代表狼。

Output

一行输出N个整数,表示若从第i只动物开始,赢的动物的种类。同上,0代表羊,1代表狼。

Sample Input 1
2 9 2
0 1
Sample Output 1
0 1
Sample Input 2
6 499 5
1 0 0 1 1 0
Sample Output 2
0 1 1 1 1 0

Sample Input 3
10 100 10
0 0 0 1 1 1 1 0 1 1
Sample Output 3
1 1 1 1 1 1 1 1 1 1
Hint

【数据范围】

对于60%的数据,1 ≤ N, M, K ≤ 500。

对于100%的数据,1 ≤ N, M, K ≤ 5000。