Byteasar 学会了一种绝妙的洗牌递归算法。该算法描述如下：

• 洗牌两张牌时，交换它们。
• 洗牌 $2^k$ 张牌（$k \ge 2$）时，将它们平分为两部分——上半部分和下半部分（每部分各有 $2^{k-1}$ 张牌）。递归地洗牌这两部分，然后将下半部分放在上半部分之上。

Byteasar 有一副 $2^n$ 张牌的牌组，每张牌上都写有一个数字。Byteasar 现在要洗这副牌，并执行上述过程恰好 $t$ 次。由于这可能需要花费大量时间，他希望预先知道洗牌后的最终顺序。

输入格式

第一行包含两个整数 $n, t$ ($1 \le n \le 20, 1 \le t \le 10^9$)。第二行包含 $2^n$ 个整数 $a_1, \dots, a_{2^n}$ ($1 \le a_i \le 10^9$)；$a_i$ 是牌组中从上往下数第 $i$ 张牌上的数字。

输出格式

在唯一的一行中输出 $2^n$ 个整数，表示 Byteasar 的牌组在经过 $t$ 次洗牌后的数字。请按从最上面到最下面的顺序打印这些数字。

样例

样例输入 1

2 1
2 4 1 5

样例输出 1

5 1 4 2