AND Масив

Задано ціле число $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
повернути res

Тут «power(2, p)» позначає $2^p$, «AND» позначає операцію побітового І, а «OR» позначає операцію побітового АБО.

Побітове І невід'ємних цілих чисел $a$ та $b$ дорівнює невід'ємному цілому числу, у якого у двійковому записі на певній позиції знаходиться одиниця тоді і тільки тоді, коли у двійкових записах $a$ та $b$ на цій позиції знаходяться одиниці. Наприклад, $3_{10}$ AND $5_{10}=0011_2$ AND $0101_2=0001_2=1_{10}$.

Побітове АБО невід'ємних цілих чисел $a$ та $b$ дорівнює невід'ємному цілому числу, у якого у двійковому записі на певній позиції знаходиться нуль тоді і тільки тоді, коли у двійкових записах $a$ та $b$ на цій позиції знаходяться нулі. Наприклад, $3_{10}$ OR $5_{10}=0011_2$ OR $0101_2=0111_2=7_{10}$.

Для кожного $i$ від $1$ до $n$ знайдіть

Вхідні дані

У першому рядку задано два цілі числа $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$ цілих чисел — шукані значення.

Приклади

Примітка

У першому прикладі $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$.

Оцінювання

1. ($10$ балів): $n\le 2000$;

2. ($10$ балів): $a_i=2^k$, де $k$ — ціле число;

3. ($15$ балів): $b\le 8$;

4. ($15$ балів): $b\le 12$;

5. ($25$ балів): $b\le 16$;

6. ($25$ балів): без додаткових обмежень.