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

문제

스도쿠는 16*16크기의 보드가 있을 때, 각 행과 각 열, 그리고 16개의 4*4 크기의 보드에 A부터 P까지 알파벳 대문자를 중복 없이 나타나도록 보드를 채우면 된다.

왼쪽 그림은 스도쿠의 초기 상태, 오른쪽 그림은 스도쿠를 푼 상태이다.

스도쿠의 초기 상태가 주어졌을 때, 스도쿠를 푼 뒤 출력하는 프로그램을 작성하시오. 항상 답이 1개인 경우만 입력으로 주어진다.

입력

스도쿠 퍼즐의 초기 상태가 주어진다. 16개 줄에 걸쳐 16개 문자가 주어진다. 빈 칸은 -로 표시한다.

출력

스도쿠 퍼즐을 푼 뒤 출력한다.

예제 입력 1

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-

예제 출력 1

FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK
W3sicHJvYmxlbV9pZCI6IjM3NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWIzYzRcdWNmZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJhNFx1YjNjNFx1Y2ZlMFx1YjI5NCAxNioxNlx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVhYzAxIFx1ZDU4OVx1YWNmYyBcdWFjMDEgXHVjNWY0LCBcdWFkZjhcdWI5YWNcdWFjZTAgMTZcdWFjMWNcdWM3NTggNCo0IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWM1ZDAgQVx1YmQ4MFx1ZDEzMCBQXHVhZTRjXHVjOWMwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjOTExXHViY2Y1IFx1YzVjNlx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwOThcdWIzYzRcdWI4NWQgXHViY2Y0XHViNGRjXHViOTdjIFx1Y2M0NFx1YzZiMFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjMmE0XHViM2M0XHVjZmUwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGMsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ3YyBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvczEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NDM2cHg7IHdpZHRoOjQ2MnB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zMi5wbmdcIiBzdHlsZT1cImhlaWdodDo0MzRweDsgd2lkdGg6NDY4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHViM2M0XHVjZmUwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ3YyBcdWI0YTQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgMVx1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDE2XHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgMTZcdWFjMWMgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZTQ4IFx1Y2U3OFx1Yzc0MCAtXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMyYTRcdWIzYzRcdWNmZTAgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3YyBcdWI0YTQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdWRva3UiLCJkZXNjcmlwdGlvbiI6IjxwPkEgU3Vkb2t1IGdyaWQgaXMgYSAxNngxNiBncmlkIG9mIGNlbGxzIGdyb3VwZWQgaW4gc2l4dGVlbiA0eDQgc3F1YXJlcywgd2hlcmUgc29tZSBjZWxscyBhcmUgZmlsbGVkIHdpdGggbGV0dGVycyBmcm9tIEEgdG8gUCAodGhlIGZpcnN0IDE2IGNhcGl0YWwgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCksIGFzIHNob3duIGluIGZpZ3VyZSAxYS4gVGhlIGdhbWUgaXMgdG8gZmlsbCBhbGwgdGhlIGVtcHR5IGdyaWQgY2VsbHMgd2l0aCBsZXR0ZXJzIGZyb20gQSB0byBQIHN1Y2ggdGhhdCBlYWNoIGxldHRlciBmcm9tIHRoZSBncmlkIG9jY3VycyBvbmNlIG9ubHkgaW4gdGhlIGxpbmUsIHRoZSBjb2x1bW4sIGFuZCB0aGUgNHg0IHNxdWFyZSBpdCBvY2N1cGllcy4gVGhlIGluaXRpYWwgY29udGVudCBvZiB0aGUgZ3JpZCBzYXRpc2ZpZXMgdGhlIGNvbnN0cmFpbnRzIG1lbnRpb25lZCBhYm92ZSBhbmQgZ3VhcmFudGVlcyBhIHVuaXF1ZSBzb2x1dGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdWRva3U0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI3NHB4OyB3aWR0aDo1ODdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIFN1ZG9rdSBwbGF5aW5nIHByb2dyYW0gdGhhdCByZWFkcyBkYXRhIHNldHMgZnJvbSBhIHRleHQgZmlsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggZGF0YSBzZXQgZW5jb2RlcyBhIGdyaWQgYW5kIGNvbnRhaW5zIDE2IHN0cmluZ3Mgb24gMTYgY29uc2VjdXRpdmUgbGluZXMgYXMgc2hvd24gaW4gZmlndXJlIDIuIFRoZSBpdGggc3RyaW5nIHN0YW5kcyBmb3IgdGhlIGl0aCBsaW5lIG9mIHRoZSBncmlkLCBpcyAxNiBjaGFyYWN0ZXJzIGxvbmcsIGFuZCBzdGFydHMgZnJvbSB0aGUgZmlyc3QgcG9zaXRpb24gb2YgdGhlIGxpbmUuIFN0cmluZyBjaGFyYWN0ZXJzIGFyZSBmcm9tIHRoZSBzZXQge0EsQiwmaGVsbGlwOyxQLC19LCB3aGVyZSAmbmRhc2g7IChtaW51cykgZGVzaWduYXRlcyBlbXB0eSBncmlkIGNlbGxzLiBUaGUgZGF0YSBzZXRzIGFyZSBzZXBhcmF0ZWQgYnkgc2luZ2xlIGVtcHR5IGxpbmVzIGFuZCB0ZXJtaW5hdGUgd2l0aCBhbiBlbmQgb2YgZmlsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgcHJvZ3JhbSBwcmludHMgdGhlIHNvbHV0aW9uIG9mIHRoZSBpbnB1dCBlbmNvZGVkIGdyaWRzIGluIHRoZSBzYW1lIGZvcm1hdCBhbmQgb3JkZXIgYXMgdXNlZCBmb3IgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d