Today Kolobok called all the wolves and foxes to visit him for tea. The tea party will take place at a round table with only n seats. Kolobok wants to seat the animals in a special way — so that wolves do not sit only with wolves, and foxes only with foxes. Therefore, for each place, he wrote down one integer — how many foxes must sit at a distance of no more than d from this place, including this place.
Two places are no more than d apart if no more than d x minus; 1 places meet between them when moving clockwise or counterclockwise from one to the other. Thus, for a given place, there are 2d + 1 places in total, located at a distance no more than d from it.
Now he wants to come up with some kind of animal seating that satisfies these restrictions.
Input
The first line contains two natural numbers n, d (3 ≤ n ≤ 10
5 , 3 ≤ 2d+1 ≤ n) — number of round table seats and distance d. The next line contains n non-negative integers ai (0 ≤ a
i ≤ 2d+1) — the number of foxes at a distance of at most d from this place, including this place. Place information is listed in circling order.
Imprint
If there is no solution, print "NO", otherwise in the first line print "YES", and in the next line print n numbers: 1 if a fox is sitting in this place, and 0 if a wolf is sitting in this place . If there are several answers, any one is allowed.
| Input |
Output |
5
1 2 2 1 2 2
| YES
1 0 1 0 1
|
9
2 3 4 4 3 3 2 2 2 2
| YES
1 0 1 1 1 0 0 0 1
|
6
1 3 3 3 3 3 1
| NO |