P4405 [ZJOI2009] Coin Game

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.

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 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.

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