Unzufrieden mit der schwachen Beleuchtung seines Stalls hat Farmer John gerade einen schicken neuen Kronleuchter mit $N$ Glühbirnen, $(3 \le N \le 16)$, installiert, die im Kreis angeordnet sind.

Die Kühe sind von der neuen Leuchte fasziniert und spielen gern folgendes Spiel: Zum Zeitpunkt $T$ schalten sie den Zustand jeder Glühbirne um, wenn ihre linke Nachbarin zum Zeitpunkt $T-1$ eingeschaltet war. Sie spielen $B$ Zeiteinheiten lang, $(1 \le B \le 10^{15})$. Beachte, dass $B$ zu groß für eine normale 32-Bit-Ganzzahl sein kann.

Bestimme aus den Anfangszuständen der Glühbirnen ihre Endzustände nach $B$ Zeiteinheiten.

Eingabe

• Zeile 1: zwei durch ein Leerzeichen getrennte ganze Zahlen $N$ und $B$.

• Zeilen $2..1+N$: Zeile $i+1$ enthält den Anfangszustand der Glühbirne $i$, entweder $0$ (aus) oder $1$ (an).

Ausgabe

• Zeilen $1..N$: Zeile $i$ soll den Endzustand der Glühbirne $i$ enthalten, entweder $0$ (aus) oder $1$ (an).

Beispiele

Eingabe 1

5 6
1
0
0
0
0

Ausgabe 1

1
1
1
0
1

Hinweis

Es gibt fünf Glühbirnen. Die erste ist anfangs eingeschaltet, die anderen sind ausgeschaltet.

Die Zustände der Glühbirnen sind wie folgt:

• Zeit $T=0$: 1 0 0 0 0

• Zeit $T=1$: 1 1 0 0 0

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

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

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

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

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

Autoren der Aufgabe: Videh Seksaria und Brian Dean, 2013