题目描述

被污染的灰灰草原上有羊和狼。有$\red{n}$只动物围成一圈，每只动物是羊或狼。

该游戏从其中的一只动物开始，报出$\red{[1,K]}$区间的整数，若上一只动物报出的数是$\red{x，}$下一只动物可以报$\red{[x+1,x+K]}$区间的整数，游戏按顺时针方向进行。

每只动物报的数字都不能超过$\red{M}$。若一只动物报了$\red{M}$这个数，它所在的种族就输了。

问以第$\red{i}$只动物为游戏的开始，最后哪种动物会赢？

输入格式

第一行输入一个正整数$\red{n，}$表示总的动物数。

接下来一行$\red{n}$个正整数，分别表示$\red{n}$只动物的种类，以顺时针的方向给出。$\red{0}$代表羊，$\red{1}$代表狼。

输出格式

一行输出$\red{n}$个整数，表示若从第$\red{i}$只动物开始，赢的动物的种类。

同上，$\red{0}$代表羊，$\red{1}$代表狼。

样例

输入样例1

2 9 2

0 1

输出样例1

0 1

输入样例2

6 499 5

1 0 0 1 1 0

输出样例2

0 1 1 1 1 0

输入样例3

10 100 10

0 0 0 1 1 1 1 0 1 1

输出样例3

1 1 1 1 1 1 1 1 1 1

提示

对于$\red{60\%}$的数据，$\red{1 ≤}$ $\red{N, M, K ≤}$ $\red{500}$。

对于$\red{100\%}$的数据，$\red{1 ≤}$ $\red{N, M, K ≤}$ $\red{5000}$。