Orez loves playing games, and he recently invented a coin game. He marks $2n$ positions on the edge of a table and labels them clockwise as $1, 2, \dots, 2n$, then places $n$ coins at the odd-numbered positions. The game proceeds in steps: in each step, a new coin is placed between every two existing coins, and then the original coins are removed. The side (heads or tails) of the newly placed coin is determined by the two coins it is placed between: if both coins are heads up or both are tails up, the new coin is heads up; otherwise, it is tails up.

What will be the state of the coins on the edge of the table after $T$ operations?

Input

The first line contains two integers $n$ and $T$.

The next line contains $n$ integers, representing the initial placement of the coins on the edge of the table. The $i$-th integer $a_i$ represents the coin placed at position $2i-1$, where $a_i=1$ means heads up and $a_i=2$ means tails up.

Output

The output contains a single line with $2n$ integers, where the $i$-th integer $b_i$ represents the state of the coin at position $i$ on the edge of the table. $b_i=1$ means heads up, $b_i=2$ means tails up, and $b_i=0$ means there is no coin.

Examples

Input 1

10 5
2 2 2 1 1 1 1 1 1 2

Output 1

0 1 0 1 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 1

Constraints

For 30% of the data: $n \le 1000, T \le 1000$

For 100% of the data: $n \le 100000, T \le 2^{60}$