시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB184423.529%

문제

"나이트"는 한국에서 엄청나게 유행하는 새 게임이다. 강산이와 창영이는 대세에 뒤쳐지지 않기 위해서 이 게임을 플레이하려고 한다. 강산이는 체스에서 사용하는 나이트 말을 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

예제 입력 2

5 6
2 3
4 5 3 2 3
1 3 4 3 1
3 4 1 3 2
4 4 2 1 3
4 6 4 9 2

예제 출력 2

5
1 4
2 1
2 5
4 5
5 2

예제 입력 3

3 3
2 2
3 6 4
2 2 5
1 3 7

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjI4MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPiZxdW90O1x1YjA5OFx1Yzc3NFx1ZDJiOCZxdW90O1x1YjI5NCBcdWQ1NWNcdWFkNmRcdWM1ZDBcdWMxMWMgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1YzcyMFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWMwYzggXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMTVcdWMwYjBcdWM3NzRcdWM2NDAgXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YjMwMFx1YzEzOFx1YzVkMCBcdWI0YTRcdWNjZDBcdWM5YzBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWNjYjRcdWMyYTRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOCBcdWI5ZDBcdWM3NDQgTipOIFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWM3MDRcdWM1ZDAgXHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViMjA4XHVhYzAwXHViOWFjXHVhYzFjXHViOTdjIFx1ZDU1OFx1YWNlMCwgXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IDFcdWNkMDhcdWM1ZDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgVFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzggXHVjNzc0XHVkNmM0XHVjNWQwLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWM3MDRcdWNlNThcdWI5N2MgXHViOWRlXHVjZDk0XHViYTc0IFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc0MCBcdWJjZjRcdWQxYjUgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWNlNzhcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWI5N2MgS1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YzljMCAwLCBLLCAySywgM2ssIC4uLlx1Y2QwOCBcdWM3NzRcdWM1YzhcdWM3NDQgXHViNTRjXHViOWNjIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0MCAwXHVjZDA4XHVjNzdjIFx1YjU0YyBcdWMyZGNcdWM3OTFcdWI0MWNcdWIyZTQuIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgOFx1YWMxYyBcdWNlNzggXHVjOTExIFx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHViYzE4XHViNGRjXHVjMmRjIFx1Yzc3NFx1YjNkOVx1YzJkY1x1Y2YxY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyZGNcdWFjMDQgXHViM2Q5XHVjNTQ4IChpXHVjZDA4IFx1Yzc3YyBcdWI1NGMsIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1Yjk3YyZuYnNwO1x1YzZjMFx1YzljMVx1YzYwMFx1YjJlNFx1YmE3NCBpKzFcdWNkMDgpIFx1YWRmOCBcdWNlNzhcdWM3NDAgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDBcdWMxMWMgVFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzggXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YWMwMCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY5Zlx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgMzAsIDEgJmxlOyBUICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IFhcdWM2NDAgWVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgWCwgWSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFRcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc4IFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMyMTggTVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjNzA0XHVjZTU4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1ZDU4OVx1Yzc3NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjLCBcdWQ1ODlcdWM3NzQgXHVhYzE5XHViMmU0XHViYTc0IFx1YzVmNFx1Yzc3NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0tBS0FDIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBwbGF5aW5nIHRoZSBwb3B1bGFyIG5ldyBnYW1lIGtub3duIGFzIFRoZSBLbmlnaHQuIE1pcmtvIHBsYWNlcyBhIGtuaWdodCBjaGVzcyBwaWVjZSBvbiBhbiBOeE4gY2hlc3Nib2FyZCBhbmQsIHdpdGggU2xhdmtvIGJsaW5kZm9sZGVkLCBtYWtlcyBleGFjdGx5IFQgbW92ZXMsIG9uZSBwZXIgc2Vjb25kLiBBZnRlciB0aGF0LCBTbGF2a28gbXVzdCBndWVzcyB0aGUgZmluYWwgcG9zaXRpb24gb2YgdGhlIGtuaWdodCBpbiBvcmRlciB0byB3aW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjaGVzc2JvYXJkIGluIHRoaXMgZ2FtZSBpcyB1bnVzdWFsIGluIHRoYXQgZWFjaCBzcXVhcmUgaXMgYmxvY2tlZCBwYXJ0IG9mIHRoZSB0aW1lLiBNb3JlIHByZWNpc2VseSwgZWFjaCBzcXVhcmUgaXMgbGFiZWxsZWQgYnkgYSBwb3NpdGl2ZSBpbnRlZ2VyLiBBIHNxdWFyZSBsYWJlbGxlZCBieSBudW1iZXIgSyBpcyBjbGVhciBvbmx5IGR1cmluZyBzZWNvbmRzIDAsIEssIDJLLCAzSyBldGM7IGl0IGlzIGJsb2NrZWQgYXQgYWxsIG90aGVyIHRpbWVzLiBUaGUga25pZ2h0IGNhbiwgb2YgY291cnNlLCBvY2N1cHkgYSBzcXVhcmUgb25seSB3aGlsZSB0aGUgc3F1YXJlIGlzIGNsZWFyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBiZWdpbnMgaW4gc2Vjb25kIDAuIEluIGVhY2ggc2Vjb25kIE1pcmtvIG11c3QgbWFrZSBhIG1vdmUgKHNlbGVjdGluZyBvbmUgb2YgOCBwb3NzaWJsZSBMc2hhcGVkIG1vdmVzLCB0d28gc3F1YXJlcyBpbiBvbmUgZGlyZWN0aW9uIGFuZCBvbmUgc3F1YXJlIGluIHRoZSBvdGhlciwgYXMgcGVyIHN0YW5kYXJkIGNoZXNzIHJ1bGVzKSwgcHJvdmlkZWQgdGhhdCB0aGUgZGVzdGluYXRpb24gc3F1YXJlIGlzIG5vdCBibG9ja2VkIGR1cmluZyB0aGUgbmV4dCBzZWNvbmQuIEhlbHAgU2xhdmtvIGJ5IHdyaXRpbmcgYSBwcm9ncmFtIHRvIGNhbGN1bGF0ZSBhbGwgcG9zc2libGUgc3F1YXJlcyB0aGF0IHRoZSBrbmlnaHQgY2FuIHBvc3NpYmx5IG9jY3VweSBhZnRlciBUIG1vdmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBOICgzICZsZTsgTiAmbGU7IDMwKSwgdGhlIHNpemUgb2YgdGhlIGNoZXNzYm9hcmQsIGFuZCBUICgxICZsZTsgVCAmbGU7IDEgMDAwIDAwMCksIHRoZSBudW1iZXIgb2YgbW92ZXMgdGhhdCBNaXJrbyB3aWxsIG1ha2UuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgWCBhbmQgWSAoMSAmbGU7IFgsIFkgJmxlOyBOKSwgdGhlIHJvdyBhbmQgY29sdW1uIGluZGljZXMgb2YgdGhlIGtuaWdodCZyc3F1bztzIHN0YXJ0aW5nIHNxdWFyZSBzZWxlY3RlZCBieSBNaXJrby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBlYWNoIGNvbnRhaW4gTiBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMTA8c3VwPjk8XC9zdXA+IChvbmUgYmlsbGlvbiksIHRoZSB2YWx1ZXMgb2YgSyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgY2hlc3Nib2FyZCBzcXVhcmVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG5vbm5lZ2F0aXZlIGludGVnZXIgTSwgdGhlIG51bWJlciBvZiBzcXVhcmVzIHRoYXQgdGhlIGtuaWdodCBjYW4gcG9zc2libHkgb2NjdXB5IGFmdGVyIFQgbW92ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE0gbGluZXMgbXVzdCBjb250YWluIGluZGljZXMgb2YgdGhvc2Ugc3F1YXJlcywgc29ydGVkIGJ5IGluY3JlYXNpbmcgcm93IGluZGV4LCB3aXRoIGNlbGxzIGluIHRoZSBzYW1lIHJvdyBzb3J0ZWQgYnkgaW5jcmVhc2luZyBjb2x1bW4gaW5kZXguJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBzdGF0ZSBvZiB0aGUgY2hlc3Nib2FyZCBpbiBlYWNoIHNlY29uZCBpcyBzaG93biBiZWxvdy4gQ2xlYXIgY2VsbHMgYXJlIGRlbm90ZWQgYnkgJmxzcXVvOy4mcnNxdW87LCBibG9ja2VkIGNlbGxzIGJ5ICZsc3F1bzsjJnJzcXVvOywgYW5kIHBvc3NpYmxlIGxvY2F0aW9ucyBvZiB0aGUga25pZ2h0IGJ5ICZsc3F1bztLJnJzcXVvOy4mbmJzcDs8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGQtY2VudGVyIHRoLWNlbnRlclwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjB0aCBzZWNvbmQ8XC90aD5cclxuXHRcdFx0PHRoPjFzdCBzZWNvbmQ8XC90aD5cclxuXHRcdFx0PHRoPjJuZCBzZWNvbmQ8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHQ8cHJlPlxyXG5LLi5cclxuLi4uXHJcbi4uLjxcL3ByZT5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0PHByZT5cclxuLiMjXHJcbiMjI1xyXG5cdTIwMGJcdTIwMGJcdTIwMGJcdTIwMGJcdTIwMGJcdTIwMGJcdTIwMGIjSy48XC9wcmU+XHJcblx0XHRcdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdDxwcmU+XHJcbksjS1xyXG4uIy5cclxuXHUyMDBiXHUyMDBiXHUyMDBiXHUyMDBiXHUyMDBiXHUyMDBiXHUyMDBiIy4uPFwvcHJlPlxyXG5cdFx0XHQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #1 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013