Недовольный тусклым освещением коровника, Farmer John только что установил красивую новую люстру из $N$ лампочек, $(3 \le N \le 16)$, расположенных по кругу.

Коровы восхищены новым светильником и любят следующую игру: в момент $T$ они переключают состояние каждой лампочки, если её соседка слева была включена в момент $T-1$. Игра продолжается $B$ единиц времени, $(1 \le B \le 10^{15})$. Учтите, что $B$ может быть слишком большим для стандартного 32-битного целого числа.

По начальным состояниям лампочек определите их конечные состояния через $B$ единиц времени.

Входные данные

• Строка 1: два целых числа, разделённых пробелом, $N$ и $B$.

• Строки $2..1+N$: строка $i+1$ содержит начальное состояние лампочки $i$: $0$ (выключена) или $1$ (включена).

Выходные данные

• Строки $1..N$: строка $i$ должна содержать конечное состояние лампочки $i$: $0$ (выключена) или $1$ (включена).

Примеры

Входные данные 1

5 6
1
0
0
0
0

Выходные данные 1

1
1
1
0
1

Примечание

Есть пять лампочек. Первая изначально включена, остальные выключены.

Состояния лампочек таковы:

• Время $T=0$: 1 0 0 0 0

• Время $T=1$: 1 1 0 0 0

• Время $T=2$: 1 0 1 0 0

• Время $T=3$: 1 1 1 1 0

• Время $T=4$: 1 0 0 0 1

• Время $T=5$: 0 1 0 0 1

• Время $T=6$: 1 1 1 0 1

Авторы задачи: Videh Seksaria и Brian Dean, 2013