AND Array

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

Let's define $f(s,p)$ ($1\le s\le n$, $0\le p<b$) as the result of 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 equal to a non-negative integer, in which the binary representation has a one at a certain position only if both binary representations of $a$ and $b$ have ones at that position. For example, $3_{10}$ AND $5_{10}=0011_2$ AND $0101_2=0001_2=1_{10}$.

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

For each $i$ from $1$ to $n$, find

Input

The first line contains two integers $n$ and $b$ ($1\le n\le 10^5$, $1\le b\le 20$) — the length of array $a$ and the limit 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 array $a$.

Output

Output $n$ integers — the required values.

Examples

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 equal to $8+9+6=23$.

Scoring

1. ($10$ points): $n\le 2000$;

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): without additional constraints.