给定一个整数 $b$ 和一个非负整数数组 $a_1, a_2, \dots, 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} \text{ AND } 5_{10} = 0011_2 \text{ AND } 0101_2 = 0001_2 = 1_{10}$。

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

对于每个 $i$ 从 $1$ 到 $n$，求： $$f(i, 0) + f(i, 1) + \dots + f(i, b - 1)$$

输入格式

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^b$)，表示数组 $a$ 的元素。

输出格式

输出 $n$ 个整数，即所求的值。

子任务

1. (10 分)：$n \le 2\,000$；
2. (10 分)：$a_i = 2^k$，其中 $k$ 为整数；
3. (15 分)：$b \le 8$；
4. (15 分)：$b \le 12$；
5. (25 分)：$b \le 16$；
6. (25 分)：无附加限制。

样例

输入 1

5 3
0 2 1 3 4

输出 1

23 20 16 14 10

输入 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$。