Given an integer $b$ and an array of non-negative integers $a_1, a_2, \dots, a_n$. All elements of the array $a$ are less than $2^b$.

Define $f(s, p)$ ($1 \le s \le n$, $0 \le p < b$) as the result of executing the following pseudocode:

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

Here, "power(2, p)" denotes $2^p$, "AND" denotes the bitwise AND operation, and "OR" denotes the bitwise OR operation.

The bitwise AND of non-negative integers $a$ and $b$ is a non-negative integer whose binary representation has a one at a certain position if and only if the binary representations of $a$ and $b$ both have a one at that position. For example, $3_{10} \text{ AND } 5_{10} = 0011_2 \text{ AND } 0101_2 = 0001_2 = 1_{10}$.

The bitwise OR of non-negative integers $a$ and $b$ is a non-negative integer whose binary representation has a zero at a certain position if and only if the binary representations of $a$ and $b$ both have a zero at that position. For example, $3_{10} \text{ OR } 5_{10} = 0011_2 \text{ OR } 0101_2 = 0111_2 = 7_{10}$.

For each $i$ from $1$ to $n$, find: $$f(i, 0) + f(i, 1) + \dots + f(i, b - 1)$$

Input

The first line contains two integers $n$ and $b$ ($1 \le n \le 10^5$, $1 \le b \le 20$) — the length of the array $a$ and the constraint on the elements of the array, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^b$) — the elements of the array $a$.

Output

Output $n$ integers — the required values.

Subtasks

1. (10 points): $n \le 2\,000$;
2. (10 points): $a_i = 2^k$, where $k$ is an integer;
3. (15 points): $b \le 8$;
4. (15 points): $b \le 12$;
5. (25 points): $b \le 16$;
6. (25 points): no additional constraints.

Examples

Input 1

5 3
0 2 1 3 4

Output 1

23 20 16 14 10

Input 2

3 2
1 3 2

Output 2

4 3 3

Note

In the first example, $f(1, 0) = 1 + 2 + 5 = 8$, $f(1, 1) = 1 + 3 + 5 = 9$, $f(1, 2) = 1 + 2 + 3 = 6$, and the first of the required values is $8 + 9 + 6 = 23$.