Niezadowolony ze słabego oświetlenia obory Farmer John właśnie zainstalował nowy ozdobny żyrandol złożony z $N$ żarówek, $(3 \le N \le 16)$, ustawionych w okręgu.

Krowy są zafascynowane nową lampą i lubią następującą grę: w chwili $T$ przełączają stan każdej żarówki, jeśli jej lewa sąsiadka była włączona w chwili $T-1$. Kontynuują grę przez $B$ jednostek czasu, $(1 \le B \le 10^{15})$. Zauważ, że $B$ może być zbyt duże, aby zmieścić się w standardowej 32-bitowej liczbie całkowitej.

Mając początkowe stany żarówek, wyznacz ich końcowe stany po upływie $B$ jednostek czasu.

Wejście

• Wiersz 1: dwie liczby całkowite rozdzielone spacją, $N$ i $B$.

• Wiersze $2..1+N$: wiersz $i+1$ zawiera początkowy stan żarówki $i$, $0$ (wyłączona) albo $1$ (włączona).

Wyjście

• Wiersze $1..N$: wiersz $i$ powinien zawierać końcowy stan żarówki $i$, $0$ (wyłączona) albo $1$ (włączona).

Przykład

Wejście 1

5 6
1
0
0
0
0

Wyjście 1

1
1
1
0
1

Uwagi

Jest pięć żarówek. Pierwsza jest początkowo włączona, a pozostałe wyłączone.

Stany żarówek są następujące:

• Czas $T=0$: 1 0 0 0 0

• Czas $T=1$: 1 1 0 0 0

• Czas $T=2$: 1 0 1 0 0

• Czas $T=3$: 1 1 1 1 0

• Czas $T=4$: 1 0 0 0 1

• Czas $T=5$: 0 1 0 0 1

• Czas $T=6$: 1 1 1 0 1

Autorzy zadania: Videh Seksaria i Brian Dean, 2013