#P18103. Game Show: XOR Edition

Game Show: XOR Edition

Game Show: XOR Edition

著名游戏节目又推出了新一季——这次是异或版!

参赛者有一个起初为空的袋子。接下来依次进行 nn 轮。每轮给出一个从 [0,2k−1][0,2^k-1] 中独立、均匀随机选出的整数,参赛者可以将它放入袋子,也可以永久放弃它。所有轮次结束后,奖金等于袋中所有数的异或和。空袋子的异或和视为 00。

参赛者知道 n,kn,k,也知道这些数的随机分布,但事先不知道具体数值。他会采用使奖金期望最大化的最优策略。如果在最优策略中,取或不取当前数字带来的期望相同,他总会选择取走它。

你是节目的制作人,已经拿到了明天会出现的整数列表;这些数确实是独立均匀随机生成的。为了节省奖金,你可以秘密改变它们出现的顺序,但不能改变数字本身。参赛者不知道你做了这件事,因此仍会采用上述策略。

请找出一种排列,使参赛者最终获得的奖金尽可能少。

输入格式

第一行包含两个整数 k,nk,n,满足

4≤k≤18,10k≤n≤2×105.4\le k\le18,\qquad 10k\le n\le2\times10^5.

这里 10k10k 表示 10×k10\times k。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 0≤ai<2k0\le a_i<2^k。保证它们是独立均匀随机生成的。

原题设置90个测试点:对每个 k=4,5,…,18k=4,5,\ldots,18,有6个测试点,其 nn 从 10k10k 到 2×1052\times10^5 按等差数列分布,包括两个端点。

输入只有一组数据。

输出格式

输出 nn 个整数,即原数组的一种排列,使参赛者最终奖金最小。如果有多种最优排列,输出任意一种。

每个数的出现次数必须与输入一致。

样例输入

4 40
4 12 3 5 9 7 0 6 13 10
12 14 14 7 2 8 3 4 2 3
4 9 13 4 13 6 10 2 0 10
4 9 15 13 10 8 6 7 14 3

原题刻意不提供样例输出,原页的 *** 只是隐藏输出的标记,不是需要输出的内容。样例输入为了排版而增加了换行,实际读入时按空白分隔即可。