시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17 3 3 18.750%

문제

"나이트"는 한국에서 엄청나게 유행하는 새 게임이다. 강산이와 창영이는 대세에 뒤쳐지지 않기 위해서 이 게임을 플레이하려고 한다. 강산이는 체스에서 사용하는 나이트 말을 N*N 체스판 위에 놓는다. 그 다음에, 창영이는 눈가리개를 하고, 강산이는 1초에 한 번씩 나이트를 T번 움직인다. 이렇게 움직인 이후에, 창영이가 나이트의 최종 위치를 맞추면 이기는 게임이다.

이 게임에서 사용하는 체스판은 보통 체스판이 아니다. 각 칸에는 숫자가 하나씩 써있다. 어떤 칸에 쓰여 있는 수를 K라고 한다면, 시작한지 0, K, 2K, 3k, ...초 이었을 때만 나이트가 이동할 수 있는 칸이다. 

게임은 0초일 때 시작된다. 강산이는 나이트를 움직일 수 있는 8개 칸 중 한 칸으로 반드시 이동시켜야 한다. 나이트가 그 자리에 있는 시간 동안 (i초 일 때, 나이트르 움직였다면 i+1초) 그 칸은 나이트가 이동할 수 있는 칸이어야 한다.

창영이를 도와서 T번 움직인 이후에 나이트가 있을 수 있는 곳의 위치를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기 N과 강산이가 나이트를 움직이는 횟수 T가 주어진다. (3 ≤ N ≤ 30, 1 ≤ T ≤ 1,000,000)

둘째 줄에는 나이트의 시작 위치 X와 Y가 주어진다. (1 ≤ X, Y ≤ N)

다음 N개 줄에는 체스판에 쓰여 있는 숫자가 주어진다. 이 값은 109보다 작거나 같은 자연수이다.

출력

첫째 줄에 T번 움직인 이후에 나이트가 있을 수 있는 곳의 위치의 수 M을 출력한다.

다음 M개 줄에는 그 위치를 한 줄에 하나씩 행이 증가하는 순서로, 행이 같다면 열이 증가하는 순서로 출력한다.

예제 입력 1

3 2
1 1
1 3 2
2 3 2
3 1 1

예제 출력 1

2
1 1
1 3

힌트

W3sicHJvYmxlbV9pZCI6IjI4MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPiZxdW90O1x1YjA5OFx1Yzc3NFx1ZDJiOCZxdW90O1x1YjI5NCBcdWQ1NWNcdWFkNmRcdWM1ZDBcdWMxMWMgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1YzcyMFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWMwYzggXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMTVcdWMwYjBcdWM3NzRcdWM2NDAgXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YjMwMFx1YzEzOFx1YzVkMCBcdWI0YTRcdWNjZDBcdWM5YzBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWNjYjRcdWMyYTRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOCBcdWI5ZDBcdWM3NDQgTipOIFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWM3MDRcdWM1ZDAgXHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViMjA4XHVhYzAwXHViOWFjXHVhYzFjXHViOTdjIFx1ZDU1OFx1YWNlMCwgXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IDFcdWNkMDhcdWM1ZDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgVFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzggXHVjNzc0XHVkNmM0XHVjNWQwLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWM3MDRcdWNlNThcdWI5N2MgXHViOWRlXHVjZDk0XHViYTc0IFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc0MCBcdWJjZjRcdWQxYjUgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzM2OFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1Y2U3OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBLXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjMmRjXHVjNzkxXHVkNTVjXHVjOWMwIDAsIEssIDJLLCAzaywgLi4uXHVjZDA4IFx1Yzc3NFx1YzVjOFx1Yzc0NCBcdWI1NGNcdWI5Y2MgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIDBcdWNkMDhcdWM3N2MgXHViNTRjIFx1YzJkY1x1Yzc5MVx1YjQxY1x1YjJlNC4gXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCA4XHVhYzFjIFx1Y2U3OCBcdWM5MTEgXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjNzc0XHViM2Q5XHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggKGlcdWNkMDggXHVjNzdjIFx1YjU0YywgXHViMDk4XHVjNzc0XHVkMmI4XHViOTc0IFx1YzZjMFx1YzljMVx1YzYwMFx1YjJlNFx1YmE3NCBpKzFcdWNkMDgpIFx1YWRmOCBcdWNlNzhcdWM3NDAgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDBcdWMxMWMgVFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzggXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YWMwMCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY5Zlx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgMzAsIDEgJmxlOyBUICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IFhcdWM2NDAgWVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgWCwgWSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFRcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc4IFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMyMTggTVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjNzA0XHVjZTU4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1ZDU4OVx1Yzc3NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjLCBcdWQ1ODlcdWM3NzQgXHVhYzE5XHViMmU0XHViYTc0IFx1YzVmNFx1Yzc3NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGVzc21hbmlhLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDo1NTdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNLQUtBQyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIFNsYXZrbyBhcmUgcGxheWluZyB0aGUgcG9wdWxhciBuZXcgZ2FtZSBrbm93biBhcyBUaGUgS25pZ2h0LiBNaXJrbyBwbGFjZXMgYSBrbmlnaHQgY2hlc3MgcGllY2Ugb24gYW4gTnhOIGNoZXNzYm9hcmQgYW5kLCB3aXRoIFNsYXZrbyBibGluZGZvbGRlZCwgbWFrZXMgZXhhY3RseSBUIG1vdmVzLCBvbmUgcGVyIHNlY29uZC4gQWZ0ZXIgdGhhdCwgU2xhdmtvIG11c3QgZ3Vlc3MgdGhlIGZpbmFsIHBvc2l0aW9uIG9mIHRoZSBrbmlnaHQgaW4gb3JkZXIgdG8gd2luLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY2hlc3Nib2FyZCBpbiB0aGlzIGdhbWUgaXMgdW51c3VhbCBpbiB0aGF0IGVhY2ggc3F1YXJlIGlzIGJsb2NrZWQgcGFydCBvZiB0aGUgdGltZS4gTW9yZSBwcmVjaXNlbHksIGVhY2ggc3F1YXJlIGlzIGxhYmVsbGVkIGJ5IGEgcG9zaXRpdmUgaW50ZWdlci4gQSBzcXVhcmUgbGFiZWxsZWQgYnkgbnVtYmVyIEsgaXMgY2xlYXIgb25seSBkdXJpbmcgc2Vjb25kcyAwLCBLLCAySywgM0sgZXRjOyBpdCBpcyBibG9ja2VkIGF0IGFsbCBvdGhlciB0aW1lcy4gVGhlIGtuaWdodCBjYW4sIG9mIGNvdXJzZSwgb2NjdXB5IGEgc3F1YXJlIG9ubHkgd2hpbGUgdGhlIHNxdWFyZSBpcyBjbGVhci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGdhbWUgYmVnaW5zIGluIHNlY29uZCAwLiBJbiBlYWNoIHNlY29uZCBNaXJrbyBtdXN0IG1ha2UgYSBtb3ZlIChzZWxlY3Rpbmcgb25lIG9mIDggcG9zc2libGUgTHNoYXBlZCBtb3ZlcywgdHdvIHNxdWFyZXMgaW4gb25lIGRpcmVjdGlvbiBhbmQgb25lIHNxdWFyZSBpbiB0aGUgb3RoZXIsIGFzIHBlciBzdGFuZGFyZCBjaGVzcyBydWxlcyksIHByb3ZpZGVkIHRoYXQgdGhlIGRlc3RpbmF0aW9uIHNxdWFyZSBpcyBub3QgYmxvY2tlZCBkdXJpbmcgdGhlIG5leHQgc2Vjb25kLiBIZWxwIFNsYXZrbyBieSB3cml0aW5nIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgYWxsIHBvc3NpYmxlIHNxdWFyZXMgdGhhdCB0aGUga25pZ2h0IGNhbiBwb3NzaWJseSBvY2N1cHkgYWZ0ZXIgVCBtb3Zlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMyAmbGU7IE4gJmxlOyAzMCksIHRoZSBzaXplIG9mIHRoZSBjaGVzc2JvYXJkLCBhbmQgVCAoMSAmbGU7IFQgJmxlOyAxIDAwMCAwMDApLCB0aGUgbnVtYmVyIG9mIG1vdmVzIHRoYXQgTWlya28gd2lsbCBtYWtlLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIFggYW5kIFkgKDEgJmxlOyBYLCBZICZsZTsgTiksIHRoZSByb3cgYW5kIGNvbHVtbiBpbmRpY2VzIG9mIHRoZSBrbmlnaHQmcnNxdW87cyBzdGFydGluZyBzcXVhcmUgc2VsZWN0ZWQgYnkgTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgZWFjaCBjb250YWluIE4gcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIDEwPHN1cD45PFwvc3VwPiAob25lIGJpbGxpb24pLCB0aGUgdmFsdWVzIG9mIEsgZm9yIHRoZSBjb3JyZXNwb25kaW5nIGNoZXNzYm9hcmQgc3F1YXJlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBub25uZWdhdGl2ZSBpbnRlZ2VyIE0sIHRoZSBudW1iZXIgb2Ygc3F1YXJlcyB0aGF0IHRoZSBrbmlnaHQgY2FuIHBvc3NpYmx5IG9jY3VweSBhZnRlciBUIG1vdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBNIGxpbmVzIG11c3QgY29udGFpbiBpbmRpY2VzIG9mIHRob3NlIHNxdWFyZXMsIHNvcnRlZCBieSBpbmNyZWFzaW5nIHJvdyBpbmRleCwgd2l0aCBjZWxscyBpbiB0aGUgc2FtZSByb3cgc29ydGVkIGJ5IGluY3JlYXNpbmcgY29sdW1uIGluZGV4LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgc3RhdGUgb2YgdGhlIGNoZXNzYm9hcmQgaW4gZWFjaCBzZWNvbmQgaXMgc2hvd24gYmVsb3cuIENsZWFyIGNlbGxzIGFyZSBkZW5vdGVkIGJ5ICZsc3F1bzsuJnJzcXVvOywgYmxvY2tlZCBjZWxscyBieSAmbHNxdW87IyZyc3F1bzssIGFuZCBwb3NzaWJsZSBsb2NhdGlvbnMgb2YgdGhlIGtuaWdodCBieSAmbHNxdW87SyZyc3F1bzsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlc3NtYW5pYS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDNweDsgd2lkdGg6NTU3cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==