문제
위 그림은 3ドル^2 \times 3^2$ 서로소 스도쿠의 예시이다.
서로소 스도쿠는 스도쿠의 변형으로 간단한 숫자 퍼즐이다. 서로소 스도쿠는 $N^2 \times N^2$ 크기의 보드에서 진행되며 각 칸에는 정수 하나를 쓸 수 있다. 이 보드를 $N \times N$ 크기의 정사각 부분으로 나눈 $N^2$개의 영역들을 '블록'이라고 한다. 서로소 스도쿠의 목표는 다음 규칙을 만족하도록 빈칸에 수를 작성하는 것이다.
모든 수는 2ドル$ 이상 1ドル,000円,000円$ 이하의 정수이다.
한 행에서 서로 다른 두 위치에 적힌 두 수 $x_1, x_2$는 서로소이다. 즉 $\gcd(x_1, x_2) = 1$이다.
한 열에서 서로 다른 두 위치에 적힌 두 수 $x_1, x_2$는 서로소이다. 즉 $\gcd(x_1, x_2) = 1$이다.
한 블록에서 서로 다른 두 위치에 적힌 두 수 $x_1, x_2$는 서로소이다. 즉 $\gcd(x_1, x_2) = 1$이다.
일부 칸이 작성된 서로소 스도쿠를 입력받았을 때, 규칙에 맞게 모든 빈칸에 수를 채우는 프로그램을 작성하시오.
출력
$N^2$개의 줄에 걸쳐 모든 빈칸을 채운 서로소 스도쿠를 출력한다. 그중 $i$번째 줄에는 $N^2$개의 정수를 공백으로 구분하여 출력한다. 이 중 $j$번째 수 $b_{ij}$는 $i$번째 행 $j$번째 열에 있는 수를 의미한다. $(2 \le b_{ij} \le 1,000円,000円)$
서로소 스도쿠의 모든 칸을 채우는 방법이 여럿인 경우는 그중 아무거나 하나를 출력한다.
예제 출력 1
복사
4 77 5 13
15 13 8 11
49 9 13 10
13 2 7 3
W3sicHJvYmxlbV9pZCI6IjI5NzU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTFjXHViODVjXHVjMThjIFx1YzJhNFx1YjNjNFx1Y2ZlMCIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjttYXgtd2lkdGg6MTAwMHB4OyBtYXJnaW46IDAgYXV0b1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMWJlOGUzOTYtN2I1NS00YzkxLThiZGYtYWUzMjQ0Y2UyMzUxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImhlaWdodDogYXV0bzsgd2lkdGg6IDEwMDBweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHVjNzA0IFx1YWRmOFx1YjliY1x1Yzc0MCAkM14yIFxcdGltZXMgM14yJCBcdWMxMWNcdWI4NWNcdWMxOGMgXHVjMmE0XHViM2M0XHVjZmUwXHVjNzU4IFx1YzYwOFx1YzJkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTFjXHViODVjXHVjMThjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1YjI5NCBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViY2MwXHVkNjE1XHVjNzNjXHViODVjIFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWMyMmJcdWM3OTAgXHVkMzdjXHVjOTkwXHVjNzc0XHViMmU0LiBcdWMxMWNcdWI4NWNcdWMxOGMgXHVjMmE0XHViM2M0XHVjZmUwXHViMjk0ICROXjIgXFx0aW1lcyBOXjIkIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjOWM0XHVkNTg5XHViNDE4XHViYTcwIFx1YWMwMSBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM0ZjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmNmNFx1YjRkY1x1Yjk3YyAkTiBcXHRpbWVzIE4kIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDEgXHViZDgwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCAkTl4yJFx1YWMxY1x1Yzc1OCBcdWM2MDFcdWM1ZWRcdWI0ZTRcdWM3NDQgJiMzOTtcdWJlMTRcdWI4NWQmIzM5O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzExY1x1Yjg1Y1x1YzE4YyBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YjJlNFx1Yzc0YyBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YmU0OFx1Y2U3OFx1YzVkMCBcdWMyMThcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0ICQyJCBcdWM3NzRcdWMwYzEgJDFcXCwwMDBcXCwwMDAkIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1ZDU1YyBcdWQ1ODlcdWM1ZDBcdWMxMWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWI0NTAgXHVjMjE4ICR4XzEsIHhfMiRcdWIyOTQgXHVjMTFjXHViODVjXHVjMThjXHVjNzc0XHViMmU0LiBcdWM5ODkgJFxcZ2NkKHhfMSwgeF8yKSA9IDEkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQ1NWMgXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM4MDFcdWQ3OGMgXHViNDUwIFx1YzIxOCAkeF8xLCB4XzIkXHViMjk0IFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVjOTg5ICRcXGdjZCh4XzEsIHhfMikgPSAxJFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkNTVjIFx1YmUxNFx1Yjg1ZFx1YzVkMFx1YzExYyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YjQ1MCBcdWMyMTggJHhfMSwgeF8yJFx1YjI5NCBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzRcdWIyZTQuIFx1Yzk4OSAkXFxnY2QoeF8xLCB4XzIpID0gMSRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzdjXHViZDgwIFx1Y2U3OFx1Yzc3NCBcdWM3OTFcdWMxMzFcdWI0MWMgXHVjMTFjXHViODVjXHVjMThjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NThcdWM3NDQgXHViNTRjLCBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViOWRlXHVhYzhjIFx1YmFhOFx1YjRlMCBcdWJlNDhcdWNlNzhcdWM1ZDAgXHVjMjE4XHViOTdjIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgyIFxcbGUgTiBcXGxlIDEwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgJE5eMiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWMxMWNcdWI4NWNcdWMxOGMgXHVjMmE0XHViM2M0XHVjZmUwIFx1YmNmNFx1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICROXjIkXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzkxMSAkaiRcdWJjODhcdWM5ZjggXHVjMjE4ICRhX3tpan0kXHViMjk0ICRpJFx1YmM4OFx1YzlmOCBcdWQ1ODkgJGokXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJGFfe2lqfSRcdWFjMDAgJDAkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHVkNTg5ICRqJFx1YmM4OFx1YzlmOCBcdWM1ZjRcdWM3NzQgXHViZTQ4XHVjZTc4XHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJCgwIFxcbGUgYV97aWp9IFxcbGUgMVxcLDAwMFxcLDAwMDskICRhX3tpan0gXFxuZXEgMSkkPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMTFjXHViODVjXHVjMThjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3MCBcdWJlNDhcdWNlNzhcdWM3NzQgXHVkNTZkXHVjMGMxICQxJFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJlNDhcdWNlNzhcdWM3NDQgXHVjYzQ0XHVjNmI4IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiROXjIkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViYWE4XHViNGUwIFx1YmU0OFx1Y2U3OFx1Yzc0NCBcdWNjNDRcdWM2YjQgXHVjMTFjXHViODVjXHVjMThjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICROXjIkXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzkxMSAkaiRcdWJjODhcdWM5ZjggXHVjMjE4ICRiX3tpan0kXHViMjk0ICRpJFx1YmM4OFx1YzlmOCBcdWQ1ODkgJGokXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJCgyIFxcbGUgYl97aWp9IFxcbGUgMVxcLDAwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1Y1x1YzE4YyBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0NCBcdWNjNDRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdmZlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVhZGY4XHVjOTExIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5NzU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29wcmltZSBTdWRva3UiLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7bWF4LXdpZHRoOjEwMDBweDsgbWFyZ2luOiAwIGF1dG9cIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzQ1YzYxMzU4LWFjY2ItNGE2ZC1hMTVhLTk5OWQ5ZWQ4YjdlN1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJoZWlnaHQ6IGF1dG87IHdpZHRoOiAxMDAwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlRoZSBpbWFnZSBhYm92ZSBleGVtcGxpZmllcyBhICQzXjIgXFx0aW1lcyAzXjIkIGNvcHJpbWUgc3Vkb2t1LjxcL3A+XHJcblxyXG48cD5Db3ByaW1lIFN1ZG9rdSBpcyBhIHNpbXBsZSB2YXJpYXRpb24gb2YgdGhlIHRyYWRpdGlvbmFsIFN1ZG9rdSBwdXp6bGUuIEl0JiMzOTtzIHBsYXllZCBvbiBhbiAkTl4yIFxcdGltZXMgTl4yJCBib2FyZCwgYW5kIGVhY2ggY2VsbCBjYW4gY29udGFpbiBvbmUgaW50ZWdlci4gVGhpcyBib2FyZCBpcyBkaXZpZGVkIGludG8gJE5eMiQgYXJlYXMgb2YgJE4gXFx0aW1lcyBOJCBjZWxscyBjYWxsZWQgJiMzOTtibG9ja3MuJiMzOTsgVGhlIGdvYWwgb2YgQ29wcmltZSBTdWRva3UgaXMgdG8gZmlsbCB0aGUgZW1wdHkgY2VsbHMgZm9sbG93aW5nIHRoZXNlIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkV2ZXJ5IG51bWJlciBpcyBhbiBpbnRlZ2VyIGJldHdlZW4gJDIkJm5ic3A7YW5kICQxXFwsMDAwXFwsMDAwJCAoaW5jbHVzaXZlKS48XC9saT5cclxuXHQ8bGk+Rm9yIHR3byBudW1iZXJzICR4XzEsIHhfMiQgd3JpdHRlbiBpbiBkaWZmZXJlbnQgcG9zaXRpb25zIGluIHRoZSBzYW1lIHJvdywgJFxcZ2NkKHhfMSwgeF8yKSA9IDEkLjxcL2xpPlxyXG5cdDxsaT5Gb3IgdHdvIG51bWJlcnMgJHhfMSwgeF8yJFx1MjAwYiB3cml0dGVuIGluIGRpZmZlcmVudCBwb3NpdGlvbnMgaW4gdGhlIHNhbWUgY29sdW1uLCAkXFxnY2QoeF8xLCB4XzIpID0gMSQuPFwvbGk+XHJcblx0PGxpPkZvciB0d28gbnVtYmVycyAkeF8xLCB4XzIkIHdyaXR0ZW4gaW4gZGlmZmVyZW50IHBvc2l0aW9ucyBpbiB0aGUgc2FtZSBibG9jaywgJFxcZ2NkKHhfMSwgeF8yKSA9IDEkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkdpdmVuIGEgcGFydGlhbGx5IGZpbGxlZCBDb3ByaW1lIFN1ZG9rdSwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmlsbHMgYWxsIHRoZSBlbXB0eSBjZWxscyBmb2xsb3dpbmcgdGhlIHJ1bGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgJE4kLiZuYnNwOyQoMiBcXGxlIE4gXFxsZSAxMCkkPFwvcD5cclxuXHJcbjxwPkZyb20gdGhlIHNlY29uZCBsaW5lIHRvICROXjIkIGxpbmVzLCB0aGUgQ29wcmltZSBTdWRva3UgYm9hcmQgaXMgZ2l2ZW4uIFRoZSAkaSQtdGggbGluZSBjb250YWlucyAkTl4yJCBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBUaGUgJGokLXRoIG51bWJlciAkYV97aWp9JFx1MjAwYiByZXByZXNlbnRzIHRoZSBudW1iZXIgaW4gdGhlICRpJC10aCByb3cgYW5kICRqJC10aCBjb2x1bW4uIElmICRhX3tpan1cdTIwMGI9MCwkIGl0IG1lYW5zIHRoZSBjZWxsIGluIHRoZSAkaSQtdGggcm93IGFuZCAkaiQtdGggY29sdW1uIGlzIGVtcHR5LiAkKDAgXFxsZSBhX3tpan0gXFxsZSAxXFwsMDAwXFwsMDAwOyQgJGFfe2lqfSBcXG5lcSAxKSQ8XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgYWx3YXlzIGZvbGxvdyB0aGUgcnVsZXMgb2YgQ29wcmltZSBTdWRva3UsIGFuZCB0aGVyZSB3aWxsIGFsd2F5cyBiZSBhdCBsZWFzdCBvbmUgZW1wdHkgY2VsbC4gVGhlcmUgYXJlIG5vIGlucHV0cyBmb3Igd2hpY2ggZmlsbGluZyB0aGUgZW1wdHkgY2VsbHMgaXMgaW1wb3NzaWJsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIENvcHJpbWUgU3Vkb2t1IG92ZXIgJE5eMiQgbGluZXMsIGZpbGxpbmcgYWxsIHRoZSBlbXB0eSBjZWxscy4gVGhlICRpJC10aCBsaW5lIHNob3VsZCBjb250YWluICROXjIkIGludGVnZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMuIFRoZSAkaiQtdGggbnVtYmVyICRiX3tpan0kXHUyMDBiIHJlcHJlc2VudHMgdGhlIG51bWJlciBpbiB0aGUgJGkkLXRoIHJvdyBhbmQgJGokLXRoIGNvbHVtbi4gJCgyIFxcbGUgYl97aWp9IFxcbGUgMVxcLDAwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBtdWx0aXBsZSBzb2x1dGlvbnMgdG8gdGhlIENvcHJpbWUgU3Vkb2t1LCB5b3UgY2FuIG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d