Bajtazar has learned a spectacular recursive card shuffling procedure. Shuffling a deck consisting of exactly two cards simply involves swapping the order of those cards. Shuffling a deck consisting of $2^k$ ($k \ge 2$) cards proceeds as follows: first, the deck is divided into two equal parts—the top and the bottom. The parts (each consisting of $2^{k-1}$ cards) are then shuffled separately and recursively, and finally, the shuffled bottom part is placed on top of the shuffled top part.

Bajtazar has a deck consisting of $2^n$ cards, each with a number written on it. Bajtazar performs the shuffle by repeating the described procedure $t$ times. He would like to know which numbers will be on the cards after all the shuffles.

Input

The first line of input contains two integers $n$ and $t$ ($1 \le n \le 20$, $1 \le t \le 10^9$). The second line of input contains $2^n$ integers $a_1, \dots, a_{2^n}$ ($1 \le a_i \le 10^9$). $a_i$ denotes the number written on the $i$-th card of Bajtazar's deck, counting from the top.

Output

In the only line of output, print $2^n$ integers representing the numbers on the cards of Bajtazar's deck after $t$ shuffles (counting from the top).

Examples

Input 1

2 1
2 4 1 5

Output 1

5 1 4 2