题目描述

给定一个整数 $b$ 和一个非负整数数组 $a_1,a_2,\ldots,a_n$。数组 $a$ 的所有元素都小于 $2^b$。

定义 $f(s, p)$ ($1\le s\le n$, $0\le p < b$) 为以下伪代码的执行结果：

res = 0
x = power(2, p)
for i = s to n:
    if ((x AND a[i]) == 0):
        x = (x OR a[i])
        res = res + i
return res

其中，power(2, p) 表示 $2^p$，AND 表示按位与运算，OR 表示按位或运算。

非负整数 $a$ 和 $b$ 的按位与运算结果是一个非负整数，其二进制表示中某一位为 1 当且仅当 $a$ 和 $b$ 的二进制表示在该位都为 1。例如，$3_{10}$ AND $5_{10} = 0011_{2}$ AND $0101_{2} = 0001_{2} = 1_{10}$。

非负整数 $a$ 和 $b$ 的按位或运算结果是一个非负整数，其二进制表示中某一位为 0 当且仅当 $a$ 和 $b$ 的二进制表示在该位都为 0。例如，$3_{10}$ OR $5_{10} = 0011_{2}$ OR $0101_{2} = 0111_{2} = 7_{10}$。

对于每个 $i$ 从 $1$ 到 $n$，计算

输入格式

第一行包含两个整数 $n$ 和 $b$ ($1 \leq n \leq 10^5$, $1 \leq b \leq 20$) —— 分别表示数组 $a$ 的长度和数组元素的限制。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < 2^b$) —— 数组 $a$ 的元素。

输出格式

输出 $n$ 个整数 —— 要求的计算结果。

输入输出样例 #1

输入 #1

5 3
0 2 1 3 4

输出 #1

23 20 16 14 10

输入输出样例 #2

输入 #2

3 2
1 3 2

输出 #2

4 3 3

说明/提示

在第一个示例中，$f(1,0)=1+2+5=8$，$f(1,1)=1+3+5=9$，$f(1,2)=1+2+3=6$，因此第一个要求的值为 $8+9+6 = 23$。

评分标准

• （10 分）：$n \leq 2\,000$；
• （10 分）：$a_i = 2^k$，其中 $k$ 为整数；
• （15 分）：$b \leq 8$；
• （15 分）：$b \leq 12$；
• （25 分）：$b \leq 16$；
• （25 分）：无额外限制。

翻译由 DeepSeek V3 完成