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

Những cô bò rất thích thú với bộ đèn mới này và vui vẻ chơi trò chơi sau: tại thời điểm \(T\), chúng đảo trạng thái của mỗi bóng đèn nếu bóng đèn bên trái nó đang bật tại thời điểm \(T-1\). Chúng tiếp tục trò 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 một 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 của chúng sau khi \(B\) đơn vị thời gian trôi qua.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(B\), cách nhau bởi một dấu cách.
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) chứa trạng thái ban đầu của bóng đèn \(i\), là 0 (tắt) hoặc 1 (bật).

Dữ liệu ra

• Các dòng từ 1 đến \(N\): dòng \(i\) chứa trạng thái cuối cùng của bóng đèn \(i\), là 0 (tắt) hoặc 1 (bật).

Ví dụ

5 6
1
0
0
0
0

1
1
1
0
1

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

Nguồn

USACO 2013 US Open, Bronze — Problem 2: Blink

Tác giả đề: Videh Seksaria và Brian Dean, 2013.