Problem Description

As we all know, goats and sheep have been fighting for years over the fields they graze. After many fierce battles, the goat leader and the sheep leader decided to meet to find a peaceful solution to their problem. After hours of discussion, they agreed to play a game for each field, with the winner gaining the right to graze that field.

The game involves a total of N animals (which can be goats or sheep) forming a circle (the exact order of goats and sheep is agreed upon by their leaders). After animal i (1 ≤ i ≤ N-1), the game continues with animal i+1, and after animal N, it continues with animal 1. The animal starting the game can say any positive integer from the interval [1, K], as long as that number does not exceed M. If the starting animal says the number j, the next animal can say a number in the interval [j+1, j+K], again not exceeding M. In other words, each animal can say a number that is at least 1 and at most K greater than the number said by the previous animal, but only if the new number does not exceed M. If an animal must say number M, its team (goats or sheep) loses.

Assuming both the goats and the sheep are playing optimally, for each i (1 ≤ i ≤ N), determine which team will win the field if the game is started by the $i^{th}$ animal.

Input Format

The first line of input contains three integers N, M, and K (1 ≤ N, M, K ≤ 5000), as described in the problem. The next line contains N numbers, where 0 indicates a sheep and 1 indicates a goat.

Output Format

Output N space-separated numbers. For each animal i (1 ≤ i ≤ N), output 0 if the sheep will win the field, and 1 if the goats will win, if the $i^{th}$ animal starts the game.

Sample Input and Output

Input Sample #1

2 9 2
0 1

Output Sample #1

0 1

Input Sample #2

6 499 5
1 0 0 1 1 0

Output Sample #2

0 1 1 1 1 0

Input Sample #3

10 100 10
0 0 0 1 1 1 1 0 1 1

Output Sample #3

1 1 1 1 1 1 1 1 1 1

Notes

In test cases worth a total of 60% of points, it will hold that 1 ≤ N, M, K ≤ 500.

Clarification of the first test case:

When a sheep starts the game, it can play as follows:

The sheep starts with number 2, after which the goat can say 3 or 4. In both cases, the sheep can say 5, after which the goat can say either 6 or 7. In both cases, the sheep can say 8, after which the goat has no choice but to say 9 and thus loses the game and the field.

见题面 Input 部分

见题面 Output 部分