题目描述

档案库中有 $n$ 份档案，第 $i$ 份档案的标签是一个可以用至多 $w$ 位二进制表示的非负整数 $a_i$。不同档案的标签可以相同。

你需要选出恰好 $k$ 个无序下标对 $(i,j)$。每个下标至多出现在一个下标对中，且每个下标对满足 $1\le i<j\le n$。

对于一个下标对 $(i,j)$，记 $d=a_i\oplus a_j$，其中 $\oplus$ 表示按位异或。它的层级定义如下：

• 若 $d=0$，层级为 $0$；
• 否则，层级为唯一满足 $2^{t-1}\le d<2^t$ 的整数 $t$。此时 $1\le t\le w$。

对于一个配对方案，令 $c_t$ 表示层级为 $t$ 的下标对数量，称

为这个方案的层级序列。

两个层级序列从左到右比较：在第一个不同的位置上，数值较大的序列更优。请计算所有合法配对方案中最优的层级序列。

输入格式

从文件 archive.in 中读取数据。

第一行输入三个整数 $n,k,w$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出到文件 archive.out 中。

输出 $w+1$ 个整数 $c_w,c_{w-1},\ldots,c_0$，表示最优的层级序列。

样例

10 5 3
0 1 4 4 5 6 6 7 7 7

2 3 0 0

样例解释

样例 #1 中，可以选择下标对 $(1,6),(2,8),(3,7),(4,9),(5,10)$。

前两个下标对的标签异或值均为 $6$，层级为 $3$；后三个下标对的标签异或值分别为 $2,3,2$，层级均为 $2$，所以得到层级序列 $(2,3,0,0)$。

层级为 $3$ 的下标对必须由最高二进制位不同的两个标签组成。输入中只有两个标签的最高位为 $0$，因此不可能得到超过两个层级为 $3$ 的下标对。其余三对的层级至多为 $2$，上述方案达到了这个上限。

数据规模与约定

对于所有数据，保证：

• $2\le n\le 2\times 10^5$；
• $1\le k\le \left\lfloor\dfrac n2\right\rfloor$；
• $1\le w\le 30$；
• $0\le a_i<2^w$，其中 $1\le i\le n$。

本题采用子任务捆绑计分：只有通过一个子任务的全部测试点，才能获得该子任务的分数。

大样例下载