You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

又到了一年一度的 $ACM-ICPC$ 邀请赛时间,又要派出队伍去参加啦！

但是今年想参加的同学人数实在是太多了，于是张老师决定让他们参加一次内部选拔赛

经过统计，张老师发现参赛人数恰好为 $2^n$ 位选手，于是他给他们依次编号为 $1 \sim 2^n$，其中第 $i$ 位同学的实力为 $a_i$

为了能够快速进行选拔，所以张老师决定进行 $n$ 轮选拔赛，选拔系数设定为 $M$，比赛规则如下：

1. 第 $i$ 轮比赛时，分组人数为 $len=2^i$，也就是会让编号为 $1 \sim len$ 的选手为第一组，编号为 $len+1 \sim 2 * len$ 的选手为第二组 $\dots$，形式化的来说，也就是每 $len$ 名选手为一组(包括被淘汰的)

2. 在划分完组以后，对于某一组来说，将组内 未被淘汰 的选手实力从高到低进行排序，然后这个组内排名 $> M$ 的选手会在本轮被淘汰（若组内人数 $\leq M$，则本组本轮全员保留）

3. 对于第 $i$ 轮比赛，在本轮所有组比赛结束后，剩余未淘汰的选手总数为 $K$，那么在本轮被淘汰的所有选手 最终比赛排名 即为 $K+1$

4. 当第 $n$ 轮比赛结束后，所有未被淘汰的选手在当前组内的排名即为他的 最终比赛排名

现在张老师想知道，所有选手的 最终比赛排名 是多少。

输入格式

输入第一行包含两个整数 $n,M$，含义如题

输入第二行包含 $2^n$ 个整数，分别表示 $a_1,a_2,a_3 \dots a_{2^n}$

输出格式

输出一行包含 $2^n$ 个整数，依次表示 $1 \sim 2^n$ 每名选手的最终比赛排名

样例 1

3 2
1 7 3 2 8 5 6 4

5 2 3 5 1 5 3 5

样例解释1

第一轮比赛分组为：$[1,7],[3,2],[8,5],[6,4]$，本轮无人淘汰

第二轮比赛分组为：$[1,7,3,2],[8,5,6,4]$ 第一组淘汰编号为 $1,4$ 的选手，第二组淘汰编号为 $6,8$ 的选手，这四位选手的最终排名为 $5$

第三轮比赛分组为 $[(1),7,3,(2),8,(5),6,(4)]$（用括号表示被淘汰的选手） 被淘汰的选手为 $3,7$，这两位选手的最终排名为 $3$

最后剩下的 $2,5$ 两位选手组内排名分别为 $2,1$，这就是他们的最终排名

样例 2

3 3
1 7 3 2 8 5 6 4

7 2 4 4 1 4 3 7

数据范围

对于所有数据满足 $n \leq 20, M \leq 2^n, 1 \leq a_i \leq 10^9$，并且保证所有选手的实力值 $a_i$ 互不相同