共有 $2^n$ 名选手参加一场编程比赛。他们的编号从 $1$ 到 $2^n$，其中编号为 $i$ 的选手的水平值为 $a_i$。保证 $a_1, a_2, \dots, a_{2^n}$ 是一个长度为 $2^n$ 的排列（即每个 $a_i$ 都是 $[1, 2^n]$ 范围内的整数，且 $a_1, a_2, \dots, a_{2^n}$ 两两不同）。

比赛采用淘汰赛制。比赛共进行 $n$ 轮；每一轮都会淘汰掉恰好一半的选手。在每一轮中，设当前剩余的选手人数为 $m$，则编号最小的选手与编号第二小的选手进行比赛，编号第三小的选手与编号第四小的选手进行比赛，以此类推。在每一场比赛中，水平值较低的选手被淘汰，而水平值较高的选手晋级下一轮。

小 D 是编号为 $x$ 的选手。他希望在比赛开始前使用魔法，以赢得尽可能多的比赛。具体来说，他最多可以执行 $k$ 次以下操作：选择两名除他自己以外的选手，并交换他们的水平值。注意，该操作只能在比赛开始前进行。

对于每个 $x = 1, 2, \dots, 2^n$，请输出他能赢得的比赛场次的最大值。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 20$) 和 $k$ ($0 \le k < 2^n$)。

第二行包含 $2^n$ 个整数 $a_1, a_2, \dots, a_{2^n}$。保证 $a$ 是一个排列。

输出格式

对于每个 $x = 1, 2, \dots, 2^n$，输出他能赢得的比赛场次的最大值。

样例

输入 1

2 1
1 2 3 4

输出 1

0 1 1 2