시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2614121681245.338%

문제

스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다. 

이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다.

  • 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
  • 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
  • 3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.

스도미노쿠의 그리드에는 1부터 9까지 숫자가 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 한다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 가능한 쌍이 모두 포함되어 있다. (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 1+2와 2+1은 같은 타일이기 때문에, 따로 구분하지 않는다. 도미노 타일은 회전 시킬 수 있다. 또, 3×3 크기의 정사각형의 경계에 걸쳐서 놓여질 수도 있다.

왼쪽 그림은 퍼즐의 초기 상태를 나타내고, 오른쪽은 퍼즐을 푼 상태이다.

스도미노쿠의 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 푸는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 주어진다. U는 도미노에 쓰여 있는 한 숫자이고, LU는 길이가 2인 문자열로 U의 위치를 나타낸다. V와 LV는 도미노에 쓰여 있는 다른 숫자를 나타낸다. 도미노의 위치는 문제에 나와있는 그림을 참고한다. 입력으로 주어지는 도미노의 각 숫자 위치는 항상 인접해 있다.

N개의 도미노의 정보가 주어진 다음 줄에는 채워져 있는 숫자의 위치가 1부터 9까지 차례대로 주어진다. 위치는 도미노의 위치를 나타낸 방법과 같은 방법으로 주어진다.

모든 도미노와 숫자가 겹치는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 퍼즐에 대해서, 스도쿠를 푼 결과를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

예제 입력 1

10
6 B2 1 B3
2 C4 9 C3
6 D3 8 E3
7 E1 4 F1
8 B7 4 B8
3 F5 2 F6
7 F7 6 F8
5 G4 9 G5
7 I8 8 I9
7 C9 2 B9
C5 A3 D9 I4 A9 E5 A2 C6 I1
11
5 I9 2 H9
6 A5 7 A6
4 B8 6 C8
3 B5 8 B4
3 C3 2 D3
9 D2 8 E2
3 G2 5 H2
1 A2 8 A1
1 H8 3 I8
8 I3 7 I4
4 I6 9 I7
I5 E6 D1 F2 B3 G9 H7 C9 E5
0

예제 출력 1

Puzzle 1
872643195
361975842
549218637
126754983
738169254
495832761
284597316
657381429
913426578
Puzzle 2
814267593
965831247
273945168
392176854
586492371
741358629
137529486
459683712
628714935
W3sicHJvYmxlbV9pZCI6IjQ1NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWIzYzRcdWJiZjhcdWIxNzhcdWNmZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJhNFx1YjNjNFx1Y2ZlMFx1YWMwMCBcdWMxMzhcdWFjYzRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzIwXHVkNTg5XHVjNzc0IFx1YjQxYyBcdWM3NzRcdWQ2YzRcdWM1ZDAsIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWQzN2NcdWM5OTBcdWM3NzQgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc3NCBcdWIwOThcdWM2NTRcdWIyZTQuIFx1YWM4Y1x1Yzc4NCBcdWI5ZTRcdWFjNzBcdWM5YzQgMjAwOVx1YjE0NCA3XHVjNmQ0XHVkNjM4XHVjNWQwXHViMjk0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1YzY0MCBcdWIzYzRcdWJiZjhcdWIxNzhcdWI5N2MgXHVkNjNjXHVkNTY5XHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc3OCBcdWMyYTRcdWIzYzRcdWJiZjhcdWIxNzhcdWNmZTBcdWFjMDAgXHVjMThjXHVhYzFjXHViNDE4XHVjNWM4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVkMzdjXHVjOTkwXHVjNzQwIFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViNTMwXHViOTc4XHViMmU0LiBcdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgOSZ0aW1lczs5IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI5N2MgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjYzQ0XHVjNmNjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMmE0XHViM2M0XHVjZmUwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjYzQ0XHVjNmNjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVkNTg5XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMSBcdWM1ZjRcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+MyZ0aW1lczszXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YjI5NCAxXHViZDgwXHVkMTMwIDlcdWFjMDBcdWM5YzAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzJhNFx1YjNjNFx1YmJmOFx1YjE3OFx1Y2ZlMFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM0ZjBcdWM1ZWNcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgNzJcdWNlNzhcdWM3NDAgXHViM2M0XHViYmY4XHViMTc4IFx1ZDBjMFx1Yzc3YyAzNlx1YWMxY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIzYzRcdWJiZjhcdWIxNzggXHVkMGMwXHVjNzdjXHVjNzQwIDFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMzBkXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiAoMSsyLCAxKzMsIDErNCwgMSs1LCAxKzYsIDErNywgMSs4LCAxKzksIDIrMywgMis0LCAyKzUsIC4uLikgMSsyXHVjNjQwIDIrMVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVkMGMwXHVjNzdjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNTMwXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjNjNFx1YmJmOFx1YjE3OCBcdWQwYzBcdWM3N2NcdWM3NDAgXHVkNjhjXHVjODA0IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIDMmdGltZXM7MyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWNiZFx1YWNjNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViMTkzXHVjNWVjXHVjOWM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3YyBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZXhhbXBsZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzUycHg7IHdpZHRoOjM1MnB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9leGFtcGxlMS1zb2xuLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM1MnB4OyB3aWR0aDozNTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMyYTRcdWIzYzRcdWJiZjhcdWIxNzhcdWNmZTBcdWM3NTggXHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHViM2M0XHViYmY4XHViMTc4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEwICZsZTsgTiAmbGU7IDM1KSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViYmY4XHViMTc4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgVSBMVSBWIExWXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gVVx1YjI5NCBcdWIzYzRcdWJiZjhcdWIxNzhcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzc0XHVhY2UwLCBMVVx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgMlx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgVVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBWXHVjNjQwIExWXHViMjk0IFx1YjNjNFx1YmJmOFx1YjE3OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWIzYzRcdWJiZjhcdWIxNzhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHVhZGY4XHViOWJjXHVjNzQ0IFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWIzYzRcdWJiZjhcdWIxNzhcdWM3NTggXHVhYzAxIFx1YzIyYlx1Yzc5MCBcdWM3MDRcdWNlNThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViM2M0XHViYmY4XHViMTc4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjNDRcdWM2Y2NcdWM4MzggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIzYzRcdWJiZjhcdWIxNzhcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWJjMjlcdWJjOTVcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIzYzRcdWJiZjhcdWIxNzhcdWM2NDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDM3Y1x1Yzk5MFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0N2MgXHVhY2IwXHVhY2ZjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDU3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1LWRvbWluby1rdSIsImRlc2NyaXB0aW9uIjoiPHA+QXMgaWYgdGhlcmUgd2VyZSBub3QgYWxyZWFkeSBlbm91Z2ggc3Vkb2t1LWxpa2UgcHV6emxlcywgdGhlIEp1bHkgMjAwOSBpc3N1ZSBvZiBHYW1lcyBNYWdhemluZSBkZXNjcmliZXMgdGhlIGZvbGxvd2luZyB2YXJpYW50IHRoYXQgY29tYmluZXMgZmFjZXRzIG9mIGJvdGggc3Vkb2t1IGFuZCBkb21pbm9zLiBUaGUgcHV6emxlIGlzIGEgZm9ybSBvZiBhIHN0YW5kYXJkIHN1ZG9rdSwgaW4gd2hpY2ggdGhlcmUgaXMgYSBuaW5lLWJ5LW5pbmUgZ3JpZCB0aGF0IG11c3QgYmUgZmlsbGVkIGluIHVzaW5nIG9ubHkgZGlnaXRzIDEgdGhyb3VnaCA5LiBJbiBhIHN1Y2Nlc3NmdWwgc29sdXRpb246PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+RWFjaCByb3cgbXVzdCBjb250YWluIGVhY2ggb2YgdGhlIGRpZ2l0cyAxIHRocm91Z2ggOS48XC9saT5cclxuXHQ8bGk+RWFjaCBjb2x1bW4gbXVzdCBjb250YWluIGVhY2ggb2YgdGhlIGRpZ2l0cyAxIHRocm91Z2ggOS48XC9saT5cclxuXHQ8bGk+RWFjaCBvZiB0aGUgaW5kaWNhdGVkIHRocmVlLWJ5LXRocmVlIHNxdWFyZXMgbXVzdCBjb250YWluIGVhY2ggb2YgdGhlIGRpZ2l0cyAxIHRocm91Z2ggOS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgYSBzdS1kb21pbm8ta3UsIG5pbmUgYXJiaXRyYXJ5IGNlbGxzIGFyZSBpbml0aWFsaXplZCB3aXRoIHRoZSBudW1iZXJzIDEgdG8gOS4gVGhpcyBsZWF2ZXMgNzIgcmVtYWluaW5nIGNlbGxzLiBUaG9zZSBtdXN0IGJlIGZpbGxlZCBieSBtYWtpbmcgdXNlIG9mIHRoZSBmb2xsb3dpbmcgc2V0IG9mIDM2IGRvbWlubyB0aWxlcy4gVGhlIHRpbGUgc2V0IGluY2x1ZGVzIG9uZSBkb21pbm8gZm9yIGVhY2ggcG9zc2libGUgcGFpciBvZiB1bmlxdWUgbnVtYmVycyBmcm9tIDEgdG8gOSAoZS5nLiwgMSsyLCAxKzMsIDErNCwgMSs1LCAxKzYsIDErNywgMSs4LCAxKzksIDIrMywgMis0LCAyKzUsIC4uLikuIE5vdGUgd2VsbCB0aGF0IHRoZXJlIGFyZSBub3Qgc2VwYXJhdGUgMSsyIGFuZCAyKzEgdGlsZXMgaW4gdGhlIHNldDsgdGhlIHNpbmdsZSBzdWNoIGRvbWlubyBjYW4gYmUgcm90YXRlZCB0byBwcm92aWRlIGVpdGhlciBvcmllbnRhdGlvbi4gQWxzbywgbm90ZSB0aGF0IGRvbWlub3MgbWF5IGNyb3NzIHRoZSBib3VuZGFyeSBvZiB0aGUgdGhyZWUtYnktdGhyZWUgc3F1YXJlcyAoYXMgZG9lcyB0aGUgMis5IGRvbWlubyBpbiBvdXIgY29taW5nIGV4YW1wbGUpLjxcL3A+XHJcblxyXG48cD5UbyBoZWxwIHlvdSBvdXQsIHdlIHdpbGwgYmVnaW4gZWFjaCBwdXp6bGUgYnkgaWRlbnRpZnlpbmcgdGhlIGxvY2F0aW9uIG9mIHNvbWUgb2YgdGhlIGRvbWlub3MuIEZvciBleGFtcGxlLCBGaWd1cmUgMSBzaG93cyBhIHNhbXBsZSBwdXp6bGUgaW4gaXRzIGluaXRpYWwgc3RhdGUuIEZpZ3VyZSAyIHNob3dzIHRoZSB1bmlxdWUgd2F5IHRvIGNvbXBsZXRlIHRoYXQgcHV6emxlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2V4YW1wbGUxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM1MnB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MzUycHhcIiBcLz48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2V4YW1wbGUxLXNvbG4ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzUycHg7IHdpZHRoOjM1MnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHB1enpsZSBkZXNjcmlwdGlvbiBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIE4sIGZvciAxMCAmbGU7IE4gJmxlOyAzNSwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgZG9taW5vcyB0aGF0IGFyZSBpbml0aWFsbHkgcGxhY2VkIGluIHRoZSBzdGFydGluZyBjb25maWd1cmF0aW9uLiBGb2xsb3dpbmcgdGhhdCBhcmUgTiBsaW5lcywgZWFjaCBkZXNjcmliaW5nIGEgc2luZ2xlIGRvbWlubyBhcyBVIExVIFYgTFYuIFZhbHVlIFUgaXMgb25lIG9mIHRoZSBudW1iZXJzIG9uIHRoZSBkb21pbm8sIGFuZCBMVSBpcyBhIHR3by1jaGFyYWN0ZXIgc3RyaW5nIHJlcHJlc2VudGluZyB0aGUgbG9jYXRpb24gb2YgdmFsdWUgVSBvbiB0aGUgYm9hcmQgYmFzZWQgb24gdGhlIGdyaWQgc3lzdGVtIGRpYWdyYW1tZWQgaW4gRmlndXJlIDEuIFRoZSB2YXJpYWJsZXMgViBhbmQgTFYgcmVwcmVzZW50aW5nIHRoZSByZXNwZWN0aXZlIHZhbHVlIGFuZCBsb2NhdGlvbiBvZiB0aGUgb3RoZXIgaGFsZiBvZiB0aGUgZG9taW5vLiBGb3IgZXhhbXBsZSwgb3VyIGZpcnN0IHNhbXBsZSBpbnB1dCBiZWluZ3Mgd2l0aCBhIGRvbWlubyBkZXNjcmliZWQgYXMgNiBCMiAxIEIzLiBUaGlzIGNvcnJlc3BvbmRzIHRvIHRoZSBkb21pbm8gd2l0aCB2YWx1ZXMgNisxIGJlaW5nIHBsYWNlZCBvbiB0aGUgYm9hcmQgc3VjaCB0aGF0IHZhbHVlIDYgaXMgaW4gcm93IEIsIGNvbHVtbiAyIGFuZCB2YWx1ZSAxIGluIHJvdyBCLCBjb2x1bW4gMy4gVGhlIHR3byBsb2NhdGlvbnMgZm9yIGEgZ2l2ZW4gZG9taW5vIHdpbGwgYWx3YXlzIGJlIG5laWdoYm9yaW5nLjxcL3A+XHJcblxyXG48cD5BZnRlciB0aGUgc3BlY2lmaWNhdGlvbiBvZiB0aGUgTiBkb21pbm9zIHdpbGwgYmUgYSBmaW5hbCBsaW5lIHRoYXQgZGVzY3JpYmVzIHRoZSBpbml0aWFsIGxvY2F0aW9ucyBvZiB0aGUgaXNvbGF0ZWQgbnVtYmVycywgb3JkZXJlZCBmcm9tIDEgdG8gOSwgdXNpbmcgdGhlIHNhbWUgcm93LWNvbHVtbiBjb252ZW50aW9ucyBmb3IgZGVzY3JpYmluZyBsb2NhdGlvbnMgb24gdGhlIGJvYXJkLiBBbGwgaW5pdGlhbCBudW1iZXJzIGFuZCBkb21pbm9zIHdpbGwgYmUgYXQgdW5pcXVlIGxvY2F0aW9ucy48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IGZpbGUgZW5kcyB3aXRoIGEgbGluZSBjb250YWluaW5nIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcHV6emxlLCBvdXRwdXQgYW4gaW5pdGlhbCBsaW5lIGlkZW50aWZ5aW5nIHRoZSBwdXp6bGUgbnVtYmVyLCBhcyBzaG93biBiZWxvdy4gRm9sbG93aW5nIHRoYXQsIG91dHB1dCB0aGUgOXg5IHN1ZG9rdSBib2FyZCB0aGF0IGNhbiBiZSBmb3JtZWQgd2l0aCB0aGUgc2V0IG9mIGRvbWlub3MuIFRoZXJlIHdpbGwgYmUgYSB1bmlxdWUgc29sdXRpb24gZm9yIGVhY2ggcHV6emxlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > Mid-Central Regional > 2011 Mid-Central Regional Programming Contest D번

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