시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 249 73 53 33.544%

문제

N개의 램프를 다음과 같은 규칙에 의해 켜고 끄려 한다.

0001 → 0011 → 0101 → 1111 → 0000 → 0000 → …

1은 램프가 켜져 있는 상태를 의미하고. 0은 꺼져 있는 상태를 의미한다. 매 초마다 램프들의 상태를 바꾸는데, 만약 전 시간에 자신의 오른 쪽 램프가 켜져 있었다면 다음 시간에 그 램프의 상태를 바꾸는 것이다. 1번 램프는 N번 램프의 오른쪽이라고 생각하자.

램프들의 모양이 주어졌을 때, M초 후의 램프들의 모양을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000), M(0 ≤ M ≤ 1,000,000,000)이 주어진다. N개의 줄에는 0 또는 1이 주어진다.

출력

N개의 줄에 램프의 상태를 출력한다.

예제 입력 1

3 1
0
0
1

예제 출력 1

0
1
1
W3sicHJvYmxlbV9pZCI6IjIyNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3YThcdWQ1MDQiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHViN2E4XHVkNTA0XHViOTdjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWNmMWNcdWFjZTAgXHViMDQ0XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+MDAwMSAmcmFycjsgMDAxMSAmcmFycjsmbmJzcDswMTAxICZyYXJyOyAxMTExICZyYXJyOyAwMDAwICZyYXJyOyZuYnNwOzAwMDAgJnJhcnI7ICZoZWxsaXA7PFwvcD5cclxuXHJcbjxwPjFcdWM3NDAgXHViN2E4XHVkNTA0XHVhYzAwIFx1Y2YxY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMC4gMFx1Yzc0MCBcdWFlYmNcdWM4MzggXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjllNCBcdWNkMDhcdWI5YzhcdWIyZTQgXHViN2E4XHVkNTA0XHViNGU0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWIyOTRcdWIzNzAsIFx1YjljY1x1YzU3ZCBcdWM4MDQgXHVjMmRjXHVhYzA0XHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM2MjRcdWI5NzggXHVjYWJkIFx1YjdhOFx1ZDUwNFx1YWMwMCBcdWNmMWNcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0XHViYTc0IFx1YjJlNFx1Yzc0YyBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVhZGY4IFx1YjdhOFx1ZDUwNFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gMVx1YmM4OCBcdWI3YThcdWQ1MDRcdWIyOTQgTlx1YmM4OCBcdWI3YThcdWQ1MDRcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHViN2E4XHVkNTA0XHViNGU0XHVjNzU4IFx1YmFhOFx1YzU5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBNXHVjZDA4IFx1ZDZjNFx1Yzc1OCBcdWI3YThcdWQ1MDRcdWI0ZTRcdWM3NTggXHViYWE4XHVjNTkxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKSwgTSgwICZsZTsgTSAmbGU7IDEsMDAwLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMCBcdWI2MTBcdWIyOTQgMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViN2E4XHVkNTA0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjI3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxhbXBzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIGNhc3RsZSB3aXRoIGEgY2lyY3VsYXIgbWFpbiBoYWxsLiBUaGVyZSBhcmUgTiBsYW1wcyBudW1iZXJlZCBmcm9tIDEgdG8gTiBvbiB0aGUgd2FsbCBvZiB0aGUgaGFsbC4gRWFjaCBvZiB0aGUgbGFtcHMgY2FuIGJlIGVpdGhlciBvbiBvciBvZmYuIEF0IGVhY2ggc2Vjb25kIHRoZSBsYW1wIG51bWJlciBpIGNoYW5nZXMgaXRzIHN0YXRlJm5ic3A7aWYgdGhlIGxhbXAgbnVtYmVyIGkrMSBpcyBvbiwgZXhjZXB0IHRoZSBsYW1wIG51bWJlciBOIGNoYW5nZXMgaXRzIHN0YXRlIGlmIHRoZSBsYW1wIG51bWJlciAxIGlzIG9uLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMsIGdpdmVuIHRoZSBpbml0aWFsIHN0YXRlcyBvZiBhbGwgbGFtcHMgYXQgc29tZSBtb21lbnQsIHRvIGZpbmQgdGhlaXIgc3RhdGVzIGFmdGVyIE0gc2Vjb25kcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiAoMCAmbHQ7IE4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pIGFuZCBNICgwICZsZTsgTSAmbGU7IDEwPHN1cD45PFwvc3VwPikuIFRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0aGUgaW5pdGlhbCBzdGF0ZXMgb2YgdGhlIGxhbXBzLCBzdGFydGluZyB3aXRoIHRoZSBsYW1wIG51bWJlciAxLiBBIGxpbmUgY29udGFpbmluZyAwIG1lYW5zIHRoYXQgdGhlIGxhbXAgaXMgb2ZmIGFuZCAxIG1lYW5zIHRoYXQgdGhlIGxhbXAgaXMgb24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBtdXN0IGNvbnRhaW4gZXhhY3RseSBOIGxpbmVzIGRlc2NyaWJpbmcgdGhlIHN0YXRlcyBvZiB0aGUgbGFtcHMgYWZ0ZXIgTSBzZWNvbmRzLCBzdGFydGluZyB3aXRoIHRoZSBsYW1wIG51bWJlciAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2003 5번