You are given a list of $n$ numbers. Each number will be 0 or 1. There must be applied $m$ iterations of the same procedure. For each iteration the value of each number will change according to:

- If the two adjacent numbers in the previous iteration are equal, the value of the number will be 0.
- Otherwise, the value of the number will be 1.

As the first and last values of the list have only one adjacent number, consider 0 to be the other adjacent number.

First line contains 2 integers $n$ and $m$ ($1\leq n \leq 1000$, $1\leq m \leq 1000 $) the amount of numbers on the list and the amount of iterations to applied respectively. Second line contains $n$ numbers separated by spaces.

Print the list of numbers after $m$ iterations.

Input

8 1
1 0 0 0 0 1 0 0

Output

0 1 0 0 1 0 1 0

Input

8 2
1 1 1 0 1 1 1 1

Output

0 0 0 0 0 1 1 0

Input

5 3
0 0 0 1 0

Output

1 0 1 0 0