Leaders

Goats and sheep have argued for years over the fields they graze. After many fierce fights, the goat leader and the sheep leader met to look for a peaceful solution. After hours of discussion they agreed to play one game for each field, and the winning team grazes that field.

The game works like this. $N$ animals, each of them a goat or a sheep, stand in a circle. The two leaders fix in advance which position holds a goat and which holds a sheep. Animal $i$ ($1 \le i \le N-1$) is followed by animal $i+1$, and animal $N$ is followed by animal $1$.

The animal that starts the game says an integer between $1$ and $K$. If the animal before it said $j$, the next animal says an integer between $j+1$ and $j+K$. In other words, each animal says a number that is greater than the previous number by at least $1$ and at most $K$. No animal may say a number greater than $M$, and the team of the animal that says $M$ loses.

Every animal plays optimally for its own team. For each $i$ ($1 \le i \le N$), determine which team takes the field when animal $i$ starts the game.

The first line contains $N$, $M$ and $K$, separated by spaces ($1 \le N, M, K \le 5000$).

The second line contains $N$ numbers separated by spaces. The $i$-th number is $0$ if animal $i$ is a sheep and $1$ if it is a goat.

Print $N$ numbers separated by spaces on one line. The $i$-th number is $0$ if the sheep take the field and $1$ if the goats take it, when animal $i$ starts the game.

In the first example the sheep starts and wins like this. The sheep says $2$, so the goat says $3$ or $4$, and in both cases the sheep can say $5$. The goat then says $6$ or $7$, and in both cases the sheep can say $8$. After that the goat has nothing left to say but $9$, so it loses the game and the field.