[AdditionalFile5213.zip](file://AdditionalFile5213.zip?type=additional_file)

#5213. 「UOI 2024 Stage 4 Day1」AND 数组

标签: 传统 | 时间限制: 6750 ms | 内存限制: 512 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day1 T4. AND Масив

我们定义 $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
返回 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

输入

5 3
0 2 1 3 4

输出

23 20 16 14 10

在第一个样例中，$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$。

样例 2

输入

3 2
1 3 2

输出

4 3 3

数据范围与提示

详细子任务附加限制及分值如下表所示：