Không hài lòng với ánh sáng mờ trong chuồng, Farmer John vừa lắp một chiếc đèn chùm mới sang trọng gồm $N$ bóng đèn, $(3 \le N \le 16)$, xếp thành vòng tròn.

Bò bị thu hút bởi bộ đèn mới và thích chơi trò sau: tại thời điểm $T$, chúng đảo trạng thái mỗi bóng đèn nếu bóng bên trái nó bật ở thời điểm $T-1$. Chúng tiếp tục chơi trong $B$ đơn vị thời gian, $(1 \le B \le 10^{15})$. Lưu ý rằng $B$ có thể quá lớn để lưu trong số nguyên 32 bit tiêu chuẩn.

Cho trạng thái ban đầu của các bóng đèn, hãy xác định trạng thái cuối cùng sau $B$ đơn vị thời gian.

Dữ liệu vào

• Dòng 1: hai số nguyên cách nhau bởi dấu cách, $N$ và $B$.

• Các dòng $2..1+N$: dòng $i+1$ chứa trạng thái ban đầu của bóng $i$, $0$ (tắt) hoặc $1$ (bật).

Dữ liệu ra

• Các dòng $1..N$: dòng $i$ phải chứa trạng thái cuối của bóng $i$, $0$ (tắt) hoặc $1$ (bật).

Ví dụ

Dữ liệu vào 1

5 6
1
0
0
0
0

Dữ liệu ra 1

1
1
1
0
1

Ghi chú

Có năm bóng đèn. Bóng đầu tiên ban đầu bật, các bóng còn lại tắt.

Trạng thái các bóng đèn như sau:

• Thời điểm $T=0$: 1 0 0 0 0

• Thời điểm $T=1$: 1 1 0 0 0

• Thời điểm $T=2$: 1 0 1 0 0

• Thời điểm $T=3$: 1 1 1 1 0

• Thời điểm $T=4$: 1 0 0 0 1

• Thời điểm $T=5$: 0 1 0 0 1

• Thời điểm $T=6$: 1 1 1 0 1

Tác giả bài toán: Videh Seksaria và Brian Dean, 2013