Insoddisfatto della scarsa illuminazione della stalla, Farmer John ha appena installato un nuovo lampadario elegante composto da $N$ lampadine, $(3 \le N \le 16)$, disposte in cerchio.

Le mucche sono affascinate dal nuovo lampadario e amano il seguente gioco: al tempo $T$ invertono lo stato di ogni lampadina se la sua vicina a sinistra era accesa al tempo $T-1$. Continuano il gioco per $B$ unità di tempo, $(1 \le B \le 10^{15})$. Nota che $B$ potrebbe essere troppo grande per un intero standard a 32 bit.

Dati gli stati iniziali delle lampadine, determina i loro stati finali dopo $B$ unità di tempo.

Input

• Riga 1: due interi separati da uno spazio, $N$ e $B$.

• Righe $2..1+N$: la riga $i+1$ contiene lo stato iniziale della lampadina $i$, $0$ (spenta) oppure $1$ (accesa).

Output

• Righe $1..N$: la riga $i$ deve contenere lo stato finale della lampadina $i$, $0$ (spenta) oppure $1$ (accesa).

Esempi

Input 1

5 6
1
0
0
0
0

Output 1

1
1
1
0
1

Nota

Ci sono cinque lampadine. La prima è inizialmente accesa e le altre sono spente.

Gli stati delle lampadine sono i seguenti:

• Tempo $T=0$: 1 0 0 0 0

• Tempo $T=1$: 1 1 0 0 0

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

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

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

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

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

Autori del problema: Videh Seksaria e Brian Dean, 2013