시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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

힌트

W3sicHJvYmxlbV9pZCI6IjI4MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPiZxdW90O1x1YjA5OFx1Yzc3NFx1ZDJiOCZxdW90O1x1YjI5NCBcdWQ1NWNcdWFkNmRcdWM1ZDBcdWMxMWMgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1YzcyMFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWMwYzggXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMTVcdWMwYjBcdWM3NzRcdWM2NDAgXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YjMwMFx1YzEzOFx1YzVkMCBcdWI0YTRcdWNjZDBcdWM5YzBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWNjYjRcdWMyYTRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOCBcdWI5ZDBcdWM3NDQgTipOIFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWM3MDRcdWM1ZDAgXHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViMjA4XHVhYzAwXHViOWFjXHVhYzFjXHViOTdjIFx1ZDU1OFx1YWNlMCwgXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IDFcdWNkMDhcdWM1ZDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgVFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzggXHVjNzc0XHVkNmM0XHVjNWQwLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWM3MDRcdWNlNThcdWI5N2MgXHViOWRlXHVjZDk0XHViYTc0IFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc0MCBcdWJjZjRcdWQxYjUgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzM2OFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1Y2U3OFx1YzVkMCBcdWMzNjhcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIEtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0XHViYTc0LCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWM5YzAgMCwgSywgMkssIDNrLCAuLi5cdWNkMDggXHVjNzc0XHVjNWM4XHVjNzQ0IFx1YjU0Y1x1YjljYyBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgMFx1Y2QwOFx1Yzc3YyBcdWI1NGMgXHVjMmRjXHVjNzkxXHViNDFjXHViMmU0LiBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHViMDk4XHVjNzc0XHVkMmI4XHViOTdjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IDhcdWFjMWMgXHVjZTc4IFx1YzkxMSBcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzRcdWIzZDlcdWMyZGNcdWNmMWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmRjXHVhYzA0IFx1YjNkOVx1YzU0OCAoaVx1Y2QwOCBcdWM3N2MgXHViNTRjLCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5NzQgXHVjNmMwXHVjOWMxXHVjNjAwXHViMmU0XHViYTc0IGkrMVx1Y2QwOCkgXHVhZGY4IFx1Y2U3OFx1Yzc0MCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViOTdjIFx1YjNjNFx1YzY0MFx1YzExYyBUXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYWE4XHViNDUwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWFjZmMgXHVhYzE1XHVjMGIwXHVjNzc0XHVhYzAwIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHVkNjlmXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMCwgMSAmbGU7IFQgJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggWFx1YzY0MCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBYLCBZICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMTA8c3VwPjk8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgVFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzggXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzU4IFx1YzIxOCBNXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOCBcdWM3MDRcdWNlNThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVkNTg5XHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI4NWMsIFx1ZDU4OVx1Yzc3NCBcdWFjMTlcdWIyZTRcdWJhNzQgXHVjNWY0XHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NoZXNzbWFuaWEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAzcHg7IHdpZHRoOjU1N3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0tBS0FDIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBwbGF5aW5nIHRoZSBwb3B1bGFyIG5ldyBnYW1lIGtub3duIGFzIFRoZSBLbmlnaHQuIE1pcmtvIHBsYWNlcyBhIGtuaWdodCBjaGVzcyBwaWVjZSBvbiBhbiBOeE4gY2hlc3Nib2FyZCBhbmQsIHdpdGggU2xhdmtvIGJsaW5kZm9sZGVkLCBtYWtlcyBleGFjdGx5IFQgbW92ZXMsIG9uZSBwZXIgc2Vjb25kLiBBZnRlciB0aGF0LCBTbGF2a28gbXVzdCBndWVzcyB0aGUgZmluYWwgcG9zaXRpb24gb2YgdGhlIGtuaWdodCBpbiBvcmRlciB0byB3aW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjaGVzc2JvYXJkIGluIHRoaXMgZ2FtZSBpcyB1bnVzdWFsIGluIHRoYXQgZWFjaCBzcXVhcmUgaXMgYmxvY2tlZCBwYXJ0IG9mIHRoZSB0aW1lLiBNb3JlIHByZWNpc2VseSwgZWFjaCBzcXVhcmUgaXMgbGFiZWxsZWQgYnkgYSBwb3NpdGl2ZSBpbnRlZ2VyLiBBIHNxdWFyZSBsYWJlbGxlZCBieSBudW1iZXIgSyBpcyBjbGVhciBvbmx5IGR1cmluZyBzZWNvbmRzIDAsIEssIDJLLCAzSyBldGM7IGl0IGlzIGJsb2NrZWQgYXQgYWxsIG90aGVyIHRpbWVzLiBUaGUga25pZ2h0IGNhbiwgb2YgY291cnNlLCBvY2N1cHkgYSBzcXVhcmUgb25seSB3aGlsZSB0aGUgc3F1YXJlIGlzIGNsZWFyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBiZWdpbnMgaW4gc2Vjb25kIDAuIEluIGVhY2ggc2Vjb25kIE1pcmtvIG11c3QgbWFrZSBhIG1vdmUgKHNlbGVjdGluZyBvbmUgb2YgOCBwb3NzaWJsZSBMc2hhcGVkIG1vdmVzLCB0d28gc3F1YXJlcyBpbiBvbmUgZGlyZWN0aW9uIGFuZCBvbmUgc3F1YXJlIGluIHRoZSBvdGhlciwgYXMgcGVyIHN0YW5kYXJkIGNoZXNzIHJ1bGVzKSwgcHJvdmlkZWQgdGhhdCB0aGUgZGVzdGluYXRpb24gc3F1YXJlIGlzIG5vdCBibG9ja2VkIGR1cmluZyB0aGUgbmV4dCBzZWNvbmQuIEhlbHAgU2xhdmtvIGJ5IHdyaXRpbmcgYSBwcm9ncmFtIHRvIGNhbGN1bGF0ZSBhbGwgcG9zc2libGUgc3F1YXJlcyB0aGF0IHRoZSBrbmlnaHQgY2FuIHBvc3NpYmx5IG9jY3VweSBhZnRlciBUIG1vdmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBOICgzICZsZTsgTiAmbGU7IDMwKSwgdGhlIHNpemUgb2YgdGhlIGNoZXNzYm9hcmQsIGFuZCBUICgxICZsZTsgVCAmbGU7IDEgMDAwIDAwMCksIHRoZSBudW1iZXIgb2YgbW92ZXMgdGhhdCBNaXJrbyB3aWxsIG1ha2UuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgWCBhbmQgWSAoMSAmbGU7IFgsIFkgJmxlOyBOKSwgdGhlIHJvdyBhbmQgY29sdW1uIGluZGljZXMgb2YgdGhlIGtuaWdodCZyc3F1bztzIHN0YXJ0aW5nIHNxdWFyZSBzZWxlY3RlZCBieSBNaXJrby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBlYWNoIGNvbnRhaW4gTiBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMTA8c3VwPjk8XC9zdXA+IChvbmUgYmlsbGlvbiksIHRoZSB2YWx1ZXMgb2YgSyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgY2hlc3Nib2FyZCBzcXVhcmVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG5vbm5lZ2F0aXZlIGludGVnZXIgTSwgdGhlIG51bWJlciBvZiBzcXVhcmVzIHRoYXQgdGhlIGtuaWdodCBjYW4gcG9zc2libHkgb2NjdXB5IGFmdGVyIFQgbW92ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE0gbGluZXMgbXVzdCBjb250YWluIGluZGljZXMgb2YgdGhvc2Ugc3F1YXJlcywgc29ydGVkIGJ5IGluY3JlYXNpbmcgcm93IGluZGV4LCB3aXRoIGNlbGxzIGluIHRoZSBzYW1lIHJvdyBzb3J0ZWQgYnkgaW5jcmVhc2luZyBjb2x1bW4gaW5kZXguJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBzdGF0ZSBvZiB0aGUgY2hlc3Nib2FyZCBpbiBlYWNoIHNlY29uZCBpcyBzaG93biBiZWxvdy4gQ2xlYXIgY2VsbHMgYXJlIGRlbm90ZWQgYnkgJmxzcXVvOy4mcnNxdW87LCBibG9ja2VkIGNlbGxzIGJ5ICZsc3F1bzsjJnJzcXVvOywgYW5kIHBvc3NpYmxlIGxvY2F0aW9ucyBvZiB0aGUga25pZ2h0IGJ5ICZsc3F1bztLJnJzcXVvOy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGVzc21hbmlhLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDo1NTdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d