Description

Orez likes playing games, and he recently invented a coin game. He divides the edge of a table into $2n$ positions and labels them clockwise as $1, 2, \ldots, 2n$, then places $n$ coins on the positions with odd labels.

Each operation is as follows: place one coin between any two coins, and then remove those two original coins. The side of the newly placed coin is determined by the two coins on its sides. If both coins are heads up or both are tails up, the new coin is heads up; otherwise, it is tails up. After performing the operation $T$ times, what will the configuration of coins along the edge of the table be.

Input Format

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

The next line contains $n$ integers, describing the initial arrangement of coins along the edge. The $i$-th integer $a_i$ gives the state of the coin placed at position $2i-1$, where $a_i = 1$ means heads up and $a_i = 2$ means tails up.

Output Format

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

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

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

Hint

30% of the testdata: $n \le 1000$, $T \le 1000$.

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

Sample explanation.

20202010101010101020
01010201010101010201
10102020101010102020
01020102010101020102
20202020201010202020
01010101020102010101

Translated by ChatGPT 5