During his school trip to Cheung Chau, Bob accidentally discovered an ancient treasure map in Cheung Po Tsai cave, which contained the locations of at most $K$ treasures on $N$ islands. He happily shared the news with his classmate Benjamin. Unexpectedly, Benjamin was greedy and tried to steal the map.

Luckily, Bob was stronger and managed to fight him off. However, during the chaos parts of the map was destroyed. Desperate, Bob came to you with the map and begged for you to help him retrieve the treasures, can you help Bob find the treasures?

The treasure map is represented by an integer array $A$ of size $N$, the $i$-th cell is denoted as $A_{i}$.

If $A_{i}=-1$, this part of the map is destroyed. Otherwise, $A_{i}$ represents the minimum distance from island $i$ to an island with treasure.
Note that the distance between island $i$ and $j$ is $|i - j|$.

You are required to find at most $K$ treasures on the map so that the map is valid.

Input

The first line contains integers $N$, $K$.
The following line contains $N$ integers $A_1,A_2,...,A_N$.

Output

If there are no possible solutions, output -1.
Else, output a line with $N$ integers, for islands with treasure, output 1, else output 0.
If there are multiple solutions, output any.

Subtasks

For all test cases,$ 1\leq K \leq N \leq 10^5$, $-1\leq A_i\leq 10^9$
Let $T_{min}$ be the minimum number of treasures required for a valid construction if it exists.
Subtask 1 (7%): $K=1$
Subtask 2 (14%): $N\leq 16$
Subtask 3 (23%): $N \leq 5000$, $K\geq 2 \times T_{min}$
Subtask 4 (19%): $K\geq 2 \times T_{min}$
Subtask 5 (37%): No additional constraints