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

문제

드록바와 셰브첸코가 첼시에서 같이 훈련하던 옛날 옛적 어느 날 두 선수는 훈련에 지쳐 다음과 같은 게임을 하며 쉬기로 한다.

편의상 두 플레이어를 A, B라고 부를 때, 두 플레이어는 N*N짜리 정사각형 보드의 한 점에서 시작하게 된다.

그래서 A, B는 각각 시작점을 가지게 되고 보드에는 흰 칸과 검은 칸이 있는데 검은 칸은 지나가지 못하는 칸이다.(물론 A, B의 시작점과 검은 칸이 겹치는 경우는 없다.)

플레이어들은 각 턴마다 상, 하, 좌, 우로 한 번씩 움직일 수 있다. 그리고 만약 플레이어가 움직여서 상대방의 현 위치와 겹치게 되면 그 플레이어는 상, 하, 좌, 우중 한 방향으로 한 번 더 움직일 수 있는 기회를 받는다.

A플레이어가 먼저 턴을 시작한다고 할 때 상대방의 시작점으로 먼저 도착하는 사람이 경기의 승자가 된다. 양 선수는 최선의 전략을 사용한다고 가정할 때 누가 승자가 될지 알아 보아라.

입력

첫째 줄에는 테스트 데이터의 개수 t (1 ≤ t ≤ 10)가 들어온다. 그리고 다음 t개의 세트에는 우선 맵의 크기 n(1 ≤ n ≤ 300)이 주어지고 다음에는 N×N짜리 지도가 주어지는데 A의 위치와 B의 위치가 표시되어있고 흰자리는 ‘.’, 검은 자리는 ‘#’으로 표시되어있다.

출력

누가 승리할지 테스트 케이스 순서대로 출력하여라.

예제 입력 1

2
4
A...
.#..
....
...B
4
A...
....
..#.
...B

예제 출력 1

B
A

힌트

첫 번째 테스트 케이스의 경우인데 A가 어떤 방향으로 움직이던 B가 따라가게 된다면 A가 3칸을 움직이고 B가 3칸째 움직이게 될 때 A의 위치와 겹칠 수 있고 그때 B가 한 번의 추가 움직임을 허용 받아 더 먼저 상대의 시작장소로 갈 수 있다. 이는 두 번째 테스트 케이스의 경우인데 이 경우 B가 어떻게 가던 A가 피해간다면 만나지 않을 수 있고 서로 만나지 않는다면 먼저 시작한 A가 승리할 수 있다.

W3sicHJvYmxlbV9pZCI6IjExOTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWM3ODQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjRkY1x1Yjg1ZFx1YmMxNFx1YzY0MCBcdWMxNzBcdWJlMGNcdWNjYjhcdWNmNTRcdWFjMDAgXHVjY2JjXHVjMmRjXHVjNWQwXHVjMTFjIFx1YWMxOVx1Yzc3NCBcdWQ2YzhcdWI4MjhcdWQ1NThcdWIzNTggXHVjNjFiXHViMGEwIFx1YzYxYlx1YzgwMSBcdWM1YjRcdWIyOTAgXHViMGEwIFx1YjQ1MCBcdWMxMjBcdWMyMThcdWIyOTQgXHVkNmM4XHViODI4XHVjNWQwIFx1YzljMFx1Y2NkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWJhNzAgXHVjMjZjXHVhZTMwXHViODVjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2I4XHVjNzU4XHVjMGMxIFx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWI5N2MgQSwgQlx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5N2MgXHViNTRjLCBcdWI0NTAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IE4qTlx1YzlkY1x1YjlhYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViY2Y0XHViNGRjXHVjNzU4IFx1ZDU1YyBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViNzk4XHVjMTFjIEEsIEJcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjOGMgXHViNDE4XHVhY2UwIFx1YmNmNFx1YjRkY1x1YzVkMFx1YjI5NCBcdWQ3NzAgXHVjZTc4XHVhY2ZjIFx1YWM4MFx1Yzc0MCBcdWNlNzhcdWM3NzQgXHVjNzg4XHViMjk0XHViMzcwIFx1YWM4MFx1Yzc0MCBcdWNlNzhcdWM3NDAgXHVjOWMwXHViMDk4XHVhYzAwXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWNlNzhcdWM3NzRcdWIyZTQuKFx1YmIzY1x1Yjg2MCBBLCBCXHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMFx1YWNmYyBcdWFjODBcdWM3NDAgXHVjZTc4XHVjNzc0IFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViNGU0XHVjNzQwIFx1YWMwMSBcdWQxMzRcdWI5YzhcdWIyZTQgXHVjMGMxLCBcdWQ1NTgsIFx1Yzg4YywgXHVjNmIwXHViODVjIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI5Y2NcdWM1N2QgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YzZjMFx1YzljMVx1YzVlY1x1YzExYyBcdWMwYzFcdWIzMDBcdWJjMjlcdWM3NTggXHVkNjA0IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWFjYjlcdWNlNThcdWFjOGMgXHViNDE4XHViYTc0IFx1YWRmOCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjMGMxLCBcdWQ1NTgsIFx1Yzg4YywgXHVjNmIwXHVjOTExIFx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1YmM4OCBcdWIzNTQgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHVkNjhjXHViOTdjIFx1YmMxYlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWJhM2NcdWM4MDAgXHVkMTM0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1YzBjMVx1YjMwMFx1YmMyOVx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3M2NcdWI4NWMgXHViYTNjXHVjODAwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzJiOVx1Yzc5MFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YzU5MSBcdWMxMjBcdWMyMThcdWIyOTQgXHVjZDVjXHVjMTIwXHVjNzU4IFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTYwIFx1YjU0YyBcdWIyMDRcdWFjMDAgXHVjMmI5XHVjNzkwXHVhYzAwIFx1YjQyMFx1YzljMCBcdWM1NGNcdWM1NDQgXHViY2Y0XHVjNTQ0XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YWMxY1x1YzIxOCB0ICgxICZsZTsgdCAmbGU7IDEwKVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGMgdFx1YWMxY1x1Yzc1OCBcdWMxMzhcdWQyYjhcdWM1ZDBcdWIyOTQgXHVjNmIwXHVjMTIwIFx1YjlmNVx1Yzc1OCBcdWQwNmNcdWFlMzAgbigxICZsZTsgbiAmbGU7IDMwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwIFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBOJnRpbWVzO05cdWM5ZGNcdWI5YWMgXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBBXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBCXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjRcdWM3ODhcdWFjZTAgXHVkNzcwXHVjNzkwXHViOWFjXHViMjk0ICZsc3F1bzsuJnJzcXVvOywgXHVhYzgwXHVjNzQwIFx1Yzc5MFx1YjlhY1x1YjI5NCAmbHNxdW87IyZyc3F1bztcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjIwNFx1YWMwMCBcdWMyYjlcdWI5YWNcdWQ1NjBcdWM5YzAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhY2JkXHVjNmIwXHVjNzc4XHViMzcwIEFcdWFjMDAgXHVjNWI0XHViNWE0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIzNTggQlx1YWMwMCBcdWI1MzBcdWI3N2NcdWFjMDBcdWFjOGMgXHViNDFjXHViMmU0XHViYTc0IEFcdWFjMDAgM1x1Y2U3OFx1Yzc0NCBcdWM2YzBcdWM5YzFcdWM3NzRcdWFjZTAgQlx1YWMwMCAzXHVjZTc4XHVjOWY4IFx1YzZjMFx1YzljMVx1Yzc3NFx1YWM4YyBcdWI0MjAgXHViNTRjIEFcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YWNiOVx1Y2U2MCBcdWMyMTggXHVjNzg4XHVhY2UwIFx1YWRmOFx1YjU0YyBCXHVhYzAwIFx1ZDU1YyBcdWJjODhcdWM3NTggXHVjZDk0XHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc4NFx1Yzc0NCBcdWQ1YzhcdWM2YTkgXHViYzFiXHVjNTQ0IFx1YjM1NCBcdWJhM2NcdWM4MDAgXHVjMGMxXHViMzAwXHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzdhNVx1YzE4Y1x1Yjg1YyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NzhcdWIzNzAgXHVjNzc0IFx1YWNiZFx1YzZiMCBCXHVhYzAwIFx1YzViNFx1YjViYlx1YWM4YyBcdWFjMDBcdWIzNTggQVx1YWMwMCBcdWQ1M2NcdWQ1NzRcdWFjMDRcdWIyZTRcdWJhNzQgXHViOWNjXHViMDk4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhY2UwIFx1YzExY1x1Yjg1YyBcdWI5Y2NcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1YmEzY1x1YzgwMCBcdWMyZGNcdWM3OTFcdWQ1NWMgQVx1YWMwMCBcdWMyYjlcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjExOTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gcGxheWVycywgQSBhbmQgQiwgcGxheSBhIGdhbWUgb24gYSBzcXVhcmUgYm9hcmQgb2Ygc2l6ZSBuICZ0aW1lczsgbi4gVGhlIHNxdWFyZXMgb2YgdGhlIGJvYXJkIGFyZSBlaXRoZXIgd2hpdGUgb3IgYmxhY2suIFRoZSBnYW1lIGlzIHBsYXllZCBvbmx5IG9uIHRoZSB3aGl0ZSBzcXVhcmVzICZtZGFzaDsgdGhlIGJsYWNrIG9uZXMgYXJlIGV4Y2x1ZGVkIGZyb20gdGhlIGdhbWUuIEVhY2ggcGxheWVyIGhhcyBvbmUgcGllY2UsIGluaXRpYWxseSBwbGFjZWQgYXQgdGhpcyBwbGF5ZXImcnNxdW87cyBzdGFydGluZyBwb2ludCAmbWRhc2g7IG9uZSBvZiB0aGUgd2hpdGUgc3F1YXJlcyBvbiB0aGUgYm9hcmQuIFRoZSBzdGFydGluZyBwb2ludCBvZiBBIGlzIGRpXHVmYjAwZXJlbnQgdGhhbiB0aGF0IG9mIEIuPFwvcD5cclxuXHJcbjxwPkluIGVhY2ggbW92ZSBhIHBsYXllciBtb3ZlcyBoaXMgcGllY2UgdG8gb25lIG9mIHRoZSBuZWlnaGJvcmluZyB3aGl0ZSBzcXVhcmVzIChlaXRoZXIgdXAsIGRvd24sIGxlZnQgb3IgcmlnaHQpLiBJZiB0aGUgcGxheWVyIG1vdmVzIGhpcyBwaWVjZSB0byB0aGUgc3F1YXJlIGN1cnJlbnRseSBvY2N1cGllZCBieSBoaXMgb3Bwb25lbnQmcnNxdW87cyBwaWVjZSwgaGUgZ2V0cyBhbiBleHRyYSBtb3ZlICh0aGlzIHdheSBoZSBqdW1wcyBvdmVyIHRoZSBvcHBvbmVudCkuIE5vdGUgdGhhdCBpbiB0aGlzIGNhc2UgdGhlIGRpcmVjdGlvbiBvZiB0aGUgc2Vjb25kIG1vdmUgY2FuIGJlIGRpXHVmYjAwZXJlbnQgdGhhbiB0aGF0IG9mIHRoZSBcdWZiMDFyc3QgbW92ZS48XC9wPlxyXG5cclxuPHA+UGxheWVyIEEgbW92ZXMgXHVmYjAxcnN0LCB0aGVuIHBsYXllcnMgYWx0ZXJuYXRlLiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBpcyB0byByZWFjaCB0aGUgb3Bwb25lbnQmcnNxdW87cyBzdGFydGluZyBwb2ludC4gVGhlIHBsYXllciB3aG9zZSBwaWVjZSByZWFjaGVzIGhpcyBvcHBvbmVudCZyc3F1bztzIHN0YXJ0aW5nIHBvaW50IFx1ZmIwMXJzdCwgd2lucyB0aGUgZ2FtZS4gRXZlbiBpZiB0aGUgcGxheWVyJnJzcXVvO3MgbGFzdCBtb3ZlIGNvbnNpc3RzIG9mIHR3byBqdW1wcywgYW5kIGhlIG9ubHkganVtcHMgb3ZlciBoaXMgb3Bwb25lbnQmcnNxdW87cyBzdGFydGluZyBwb2ludCAoc2luY2UgaXQgaXMgb2NjdXBpZWQgYnkgaGlzIG9wcG9uZW50KSwgdGhlIHBsYXllciB3aW5zLiBXZSB3YW50IHRvIGRldGVybWluZSB3aGljaCBwbGF5ZXIgaGFzIGEgd2lubmluZyBzdHJhdGVneSAoYSBwbGF5ZXIgaGFzIGEgd2lubmluZyBzdHJhdGVneSBpZiBoZSBjYW4gd2luIHJlZ2FyZGxlc3Mgb2YgaGlzIG9wcG9uZW50JnJzcXVvO3MgbW92ZXMpLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6IDEwMCU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDogNTAlOyB0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9hNDBlY2MxNS0zYTlhLTRhMDUtYjdlZi05YzczMGNlNTVlYTZcLy1cL2Nyb3BcLzI4M3gyODZcLzAsMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTQycHg7IGhlaWdodDogMTQzcHg7XCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOiA1MCU7IHRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2E0MGVjYzE1LTNhOWEtNGEwNS1iN2VmLTljNzMwY2U1NWVhNlwvLVwvY3JvcFwvMjgxeDI4NlwvNjE1LDBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE0MXB4OyBoZWlnaHQ6IDE0M3B4O1wiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOiA1MCU7XCI+RmlndXJlIDEuIElmIEEgbW92ZXMgdG8gdGhlIHJpZ2h0IG9uIGhpcyBmaXJzdCB0aHJlZSBtb3ZlcywgQiB3aWxsIG1vdmUgdXAgdGhlIGZpcnN0IHRocmVlIG1vdmVzLiBUaHVzLCBvbiB0aGUgdGhpcmQgbW92ZSBwbGF5ZXIgQiB3aWxsIHJlYWNoIHRoZSBzcXVhcmUgd2l0aCBBJnJzcXVvO3MgcGllY2UgYW5kIHdpbGwgYmUgYWxsb3dlZCB0byBtb3ZlIGFnYWluLiBCZWNhdXNlIG9mIHRoaXMsIEIgd2lsbCByZWFjaCBBJnJzcXVvO3Mgc3RhcnRpbmcgcG9pbnQgZmlyc3QgYW5kIHdpbGwgd2luIHRoZSBnYW1lLjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDogNTAlO1wiPkZpZ3VyZSAyLiBBIGNhbiBzdGFydCBieSBtb3Zpbmcgb25lIHN0ZXAgdG8gdGhlIHJpZ2h0IGFuZCBvbmUgc3RlcCBkb3duLiBUaGVuLCBkZXBlbmRpbmcgb24gdGhlIGZpcnN0IHR3byBtb3ZlcyBvZiBCLCBoZSB3aWxsIGVpdGhlciBnbyBkb3duIG9yIHJpZ2h0IGFuZCBldmFkZSBCLiBUaGlzIHdheSBBIHdpbGwgcmVhY2ggQiZyc3F1bztzIHN0YXJ0aW5nIHBvaW50IGZpcnN0LCB0aHVzIHdpbm5pbmcgdGhlIGdhbWUuIEluIGZhY3Qgd2UgcHJvdmVkIHRoYXQgQSBoYXMgYSB3aW5uaW5nIHN0cmF0ZWd5LjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtLCB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBsYXlvdXQgb2YgdGhlIGdyaWQgYW5kIHRoZSBzdGFydGluZyBwb2ludHMgb2YgdGhlIHR3byBwbGF5ZXJzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5cdWZiMDFuZHMgdGhlIHBsYXllciB3aG8gaGFzIGEgd2lubmluZyBzdHJhdGVneSw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIHQgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICgxICZsZTsgdCAmbGU7IDEwKS4gQWZ0ZXIgaXQgdGhlIGRlc2NyaXB0aW9uIG9mIHQgdGVzdHMgYXBwZWFycy4gRWFjaCB0ZXN0IGlzIGRlc2NyaWJlZCBhcyBmb2xsb3dzLiBJbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgdGVzdCB0aGVyZSBpcyBvbmUgaW50ZWdlciBuICgyICZsZTsgbiAmbGU7IDMwMCksIHRoZSBsZW5ndGggb2YgdGhlIHNpZGUgb2YgdGhlIGdyaWQuIFRoZW4gbmV4dCBuIGxpbmVzIGNvbnRhaW4gdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBncmlkLiBFYWNoIGxpbmUgY29uc2lzdHMgb2YgbiBjaGFyYWN0ZXJzICh3aXRoIG5vIHdoaXRlc3BhY2VzIGJldHdlZW4gdGhlbSkuIEVhY2ggY2hhcmFjdGVyIGlzIGVpdGhlciAmcnNxdW87PGNvZGU+LjxcL2NvZGU+JnJzcXVvOyAoYSB3aGl0ZSBzcXVhcmUpLCAmcnNxdW87PGNvZGU+IzxcL2NvZGU+JnJzcXVvOyAoYSBibGFjayBzcXVhcmUpLCAmcnNxdW87PGNvZGU+QTxcL2NvZGU+JnJzcXVvOyAodGhlIHN0YXJ0aW5nIHBvaW50IG9mIEEpIG9yICZyc3F1bzs8Y29kZT5CPFwvY29kZT4mcnNxdW87ICh0aGUgc3RhcnRpbmcgcG9pbnQgb2YgQikuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgdGhlcmUgZXhpc3RzIGEgcGF0aCBvZiB3aGl0ZSBzcXVhcmVzIGJldHdlZW4gdGhlIHN0YXJ0aW5nIHBvaW50cyBvZiBBIGFuZCBCLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBleGFjdGx5IG9uZSBsaW5lIHNob3VsZCBiZSBwcmludGVkIHRvIHN0YW5kYXJkIG91dHB1dCBjb250YWluaW5nIGEgc2luZ2xlIGNoYXJhY3RlciAmcnNxdW87PGNvZGU+QTxcL2NvZGU+JnJzcXVvOyBvciAmcnNxdW87PGNvZGU+QjxcL2NvZGU+JnJzcXVvOywgaW5kaWNhdGluZyB0aGUgcGxheWVyIHdobyBoYXMgYSB3aW5uaW5nIHN0cmF0ZWd5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 1번

  • 문제를 번역한 사람: author4