Mécontent du faible éclairage de son étable, Farmer John vient d’installer un nouveau lustre élégant composé de $N$ ampoules, $(3 \le N \le 16)$, disposées en cercle.

Les vaches sont fascinées par ce nouveau luminaire et aiment jouer au jeu suivant : à l’instant $T$, elles inversent l’état de chaque ampoule si sa voisine de gauche était allumée à l’instant $T-1$. Elles continuent ce jeu pendant $B$ unités de temps, $(1 \le B \le 10^{15})$. Attention : $B$ peut être trop grand pour un entier standard de 32 bits.

Étant donnés les états initiaux des ampoules, déterminez leurs états finaux après $B$ unités de temps.

Entrée

• Ligne 1 : deux entiers séparés par une espace, $N$ et $B$.

• Lignes $2..1+N$ : la ligne $i+1$ contient l’état initial de l’ampoule $i$, soit $0$ (éteinte), soit $1$ (allumée).

Sortie

• Lignes $1..N$ : la ligne $i$ doit contenir l’état final de l’ampoule $i$, soit $0$ (éteinte), soit $1$ (allumée).

Exemples

Entrée 1

5 6
1
0
0
0
0

Sortie 1

1
1
1
0
1

Remarque

Il y a cinq ampoules. La première est initialement allumée et les autres sont éteintes.

Les états des ampoules sont les suivants :

• Instant $T=0$: 1 0 0 0 0

• Instant $T=1$: 1 1 0 0 0

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

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

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

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

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

Auteurs du problème : Videh Seksaria et Brian Dean, 2013