시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1181 609 490 52.632%

문제

로봇은 명령어를 읽어들여 정사각형 영역 S를 x축 또는 y축과 평행한 방향으로 움직인다. S의 왼쪽 아래 꼭짓점은 (0, 0)이고, 오른쪽 위의 꼭짓점은 (M, M)이다. 처음에 로봇은 (0, 0)에 위치해 있고, 동쪽 방향을 향하고 있다.

명령어는 로봇이 현재 위치에서 행할 동작과 그 동작과 관련된 값으로 주어진다. 동작은 두 가지가 있는데, TURNMOVE이다. TURN 0 명령은 현재 위치에서 왼쪽으로 90도 회전, TURN 1 명령은 현재 위치에서 오른쪽으로 90도 회전을 의미한다. MOVE d 명령은 로봇이 향하고 있는 방향으로 d만큼 움직이는 것을 의미한다. 여기서 d는 양수이다.

명령의 수행 후 로봇이 S의 경계 또는 내부에 있으면 이 명령어는 유효하다. 만일 명령어 수행 후 로봇이 S의 바깥으로 완전히 나가게 된다면 명령어는 유효하지 않다. 일련의 명령어 열을 이루는 각 명령어가 모두 유효하다면, 이 명령어 열을 유효하다고 한다.

예를 들어 로봇이 왼쪽 그림과 같이 (MOVE 6, TURN 0, MOVE 5, TURN 0, MOVE 2, TURN 0, MOVE 2, TURN 0, MOVE 4, TURN 0, MOVE 3, MOVE 2) 명령어를 읽어들인다면, 최종적으로 로봇은 (8, 8) 위치에 있게 된다. 가운데 그림과 같이 (MOVE 10, TURN 0, MOVE 2, TURN 0, MOVE 5, TURN 1, MOVE 5, TURN 1, MOVE 2, TURN 1, MOVE 3, TURN 0, TURN 0, MOVE 6) 명령어를 읽어들인다면, 로봇은 (7, 10)에 위치하게 된다. 오른쪽 그림과 같이 로봇이 S 바깥으로 나간다면, 명령어 열은 유효하지 않다.

그림 1. M = 11일 때 세 가지 명령어 열을 받은 로봇의 경로

한 변의 길이가 M인 정사각형과 n개의 명령어, 그리고 로봇이 (0, 0) 위치에서 시작해 동쪽을 바라보고 있을 때, n개의 명령어를 따라 움직였을 때 최종 위치를 출력하는 프로그램을 작성하라.

입력

입력은 표준 입력으로부터 받는다. 첫 줄에는 두 정수 M과 n (1 ≤ M ≤ 1,000, 1 ≤ n ≤ 1,000)이 주어진다. M은 정사각형 S의 한 변의 길이, 즉 오른쪽 맨 위의 좌표는 (M, M)이 된다. n은 로봇이 수행할 n개의 명령어이다. 그 다음 n개의 줄에는 명령어가 하나씩 주어진다. 각 명령어는 TURNdir 또는 MOVEd의 쌍으로 주어진다. 여기서 dir은 0 또는 1이며 d는 1,000 이하의 양의 정수이다. 로봇의 처음 위치는 (0, 0)이며 동쪽을 바라보고 있음에 유의하라.

출력

표준 출력으로 정확히 한 줄을 출력한다. 명령어 열이 유효하다면 두 음 아닌 정수를 출력하며, 이는 각각 명령어 수행 후 로봇의 위치의 x좌표와 y좌표이고 빈 칸으로 구분되어 있다. 명령어 열이 유효하지 않다면 -1을 출력한다.

예제 입력 1

11 14
MOVE 10
TURN 0
MOVE 2
TURN 0
MOVE 5
TURN 1
MOVE 5
TURN 1
MOVE 2
TURN 1
MOVE 3
TURN 0
TURN 0
MOVE 6

예제 출력 1

7 10

예제 입력 2

11 7
MOVE 5
TURN 0
MOVE 4
TURN 1
MOVE 2
TURN 1
MOVE 5

예제 출력 2

-1

예제 입력 3

2 7
MOVE 2
TURN 0
MOVE 3
TURN 0
MOVE 2
TURN 0
MOVE 2

예제 출력 3

-1
W3sicHJvYmxlbV9pZCI6IjEzNTY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViODVjXHViZDA3IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI4NWNcdWJkMDdcdWM3NDAgXHViYTg1XHViODM5XHVjNWI0XHViOTdjIFx1Yzc3ZFx1YzViNFx1YjRlNFx1YzVlYyZuYnNwO1x1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWQgU1x1Yjk3YyB4XHVjZDk1IFx1YjYxMFx1YjI5NCB5XHVjZDk1XHVhY2ZjIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LiBTXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwICgwLCAwKVx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNFx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgKE0sIE0pXHVjNzc0XHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDAgXHViODVjXHViZDA3XHVjNzQwICgwLCAwKVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NzQgXHVjNzg4XHVhY2UwLCBcdWIzZDlcdWNhYmQgXHViYzI5XHVkNWE1XHVjNzQ0IFx1ZDVhNVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE4NVx1YjgzOVx1YzViNFx1YjI5NCBcdWI4NWNcdWJkMDdcdWM3NzQgXHVkNjA0XHVjN2FjIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWQ1ODlcdWQ1NjAgXHViM2Q5XHVjNzkxXHVhY2ZjIFx1YWRmOCBcdWIzZDlcdWM3OTFcdWFjZmMgXHVhZDAwXHViODI4XHViNDFjIFx1YWMxMlx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjNkOVx1Yzc5MVx1Yzc0MCBcdWI0NTAgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwmbmJzcDs8Y29kZT5UVVJOPFwvY29kZT5cdWFjZmMgPGNvZGU+TU9WRTxcL2NvZGU+XHVjNzc0XHViMmU0LiA8Y29kZT5UVVJOIDA8XC9jb2RlPiBcdWJhODVcdWI4MzlcdWM3NDAgXHVkNjA0XHVjN2FjIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgOTBcdWIzYzQgXHVkNjhjXHVjODA0LCA8Y29kZT5UVVJOIDE8XC9jb2RlPiBcdWJhODVcdWI4MzlcdWM3NDAgXHVkNjA0XHVjN2FjIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgOTBcdWIzYzQgXHVkNjhjXHVjODA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gPGNvZGU+TU9WRSBkPFwvY29kZT4gXHViYTg1XHViODM5XHVjNzQwIFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWQ1YTVcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBkXHViOWNjXHVkMDdjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgZFx1YjI5NCBcdWM1OTFcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE4NVx1YjgzOVx1Yzc1OCBcdWMyMThcdWQ1ODkgXHVkNmM0IFx1Yjg1Y1x1YmQwN1x1Yzc3NCBTXHVjNzU4IFx1YWNiZFx1YWNjNCBcdWI2MTBcdWIyOTQgXHViMGI0XHViZDgwXHVjNWQwIFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM3NzQgXHViYTg1XHViODM5XHVjNWI0XHViMjk0IFx1YzcyMFx1ZDZhOFx1ZDU1OFx1YjJlNC4gXHViOWNjXHVjNzdjIFx1YmE4NVx1YjgzOVx1YzViNCBcdWMyMThcdWQ1ODkgXHVkNmM0Jm5ic3A7XHViODVjXHViZDA3XHVjNzc0IFNcdWM3NTggXHViYzE0XHVhZTY1XHVjNzNjXHViODVjIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIwOThcdWFjMDBcdWFjOGMgXHViNDFjXHViMmU0XHViYTc0IFx1YmE4NVx1YjgzOVx1YzViNFx1YjI5NCBcdWM3MjBcdWQ2YThcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWM3N2NcdWI4MjhcdWM3NTggXHViYTg1XHViODM5XHVjNWI0IFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVhYzAxIFx1YmE4NVx1YjgzOVx1YzViNFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjNzIwXHVkNmE4XHVkNTU4XHViMmU0XHViYTc0LCBcdWM3NzQgXHViYTg1XHViODM5XHVjNWI0IFx1YzVmNFx1Yzc0NCBcdWM3MjBcdWQ2YThcdWQ1NThcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCAoPGNvZGU+TU9WRSA2LCBUVVJOIDAsIE1PVkUgNSwgVFVSTiAwLCBNT1ZFIDIsIFRVUk4gMCwgTU9WRSAyLCBUVVJOIDAsIE1PVkUgNCwgVFVSTiAwLCBNT1ZFIDMsIE1PVkUgMjxcL2NvZGU+KSBcdWJhODVcdWI4MzlcdWM1YjRcdWI5N2MgXHVjNzdkXHVjNWI0XHViNGU0XHVjNzc4XHViMmU0XHViYTc0LCBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHViODVjXHViZDA3XHVjNzQwICg4LCA4KSBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHVjNmI0XHViMzcwIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQmbmJzcDsoPGNvZGU+TU9WRSAxMCwgVFVSTiAwLCBNT1ZFIDIsIFRVUk4gMCwgTU9WRSA1LCBUVVJOIDEsIE1PVkUgNSwgVFVSTiAxLCBNT1ZFIDIsIFRVUk4gMSwgTU9WRSAzLCBUVVJOIDAsIFRVUk4gMCwgTU9WRSA2PFwvY29kZT4pIFx1YmE4NVx1YjgzOVx1YzViNFx1Yjk3YyBcdWM3N2RcdWM1YjRcdWI0ZTRcdWM3NzhcdWIyZTRcdWJhNzQsIFx1Yjg1Y1x1YmQwN1x1Yzc0MCAoNywgMTApXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Yjg1Y1x1YmQwN1x1Yzc3NCBTIFx1YmMxNFx1YWU2NVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDRcdWIyZTRcdWJhNzQsIFx1YmE4NVx1YjgzOVx1YzViNCBcdWM1ZjRcdWM3NDAmbmJzcDtcdWM3MjBcdWQ2YThcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91c2VydXBsb2FkXC90b3BvbG9neVwvMjAxNjExMDZcLzI3Zjc4ODRjOTlmN2M2NmQ5NTJhMTEwMjI5NmI0ZDYyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyOHB4OyB3aWR0aDo2MzhweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdWFkZjhcdWI5YmMgMS4gTSA9IDExXHVjNzdjIFx1YjU0YyBcdWMxMzggXHVhYzAwXHVjOWMwIFx1YmE4NVx1YjgzOVx1YzViNCBcdWM1ZjRcdWM3NDQgXHViYzFiXHVjNzQwIFx1Yjg1Y1x1YmQwN1x1Yzc1OCBcdWFjYmRcdWI4NWM8XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgTVx1Yzc3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWFjZmMgblx1YWMxY1x1Yzc1OCBcdWJhODVcdWI4MzlcdWM1YjQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI4NWNcdWJkMDdcdWM3NzQgKDAsIDApIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzQgXHViM2Q5XHVjYWJkXHVjNzQ0IFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBuXHVhYzFjXHVjNzU4IFx1YmE4NVx1YjgzOVx1YzViNFx1Yjk3YyBcdWI1MzBcdWI3N2MgXHVjNmMwXHVjOWMxXHVjNjAwXHVjNzQ0IFx1YjU0YyBcdWNkNWNcdWM4ODUgXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHViYzFiXHViMjk0XHViMmU0LiBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHViNDUwIFx1YzgxNVx1YzIxOCBNXHVhY2ZjJm5ic3A7biAoMSAmbGU7IE0gJmxlOyAxLDAwMCwgMSAmbGU7IG4gJmxlOyAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBNXHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBTXHVjNzU4IFx1ZDU1YyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0LCBcdWM5ODkgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjllOCBcdWM3MDRcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IChNLCBNKVx1Yzc3NCBcdWI0MWNcdWIyZTQuIG5cdWM3NDAgXHViODVjXHViZDA3XHVjNzc0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBuXHVhYzFjXHVjNzU4IFx1YmE4NVx1YjgzOVx1YzViNFx1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhODVcdWI4MzlcdWM1YjRcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmE4NVx1YjgzOVx1YzViNFx1YjI5NCA8Y29kZT5UVVJOPFwvY29kZT5cdWFjZmMgPGNvZGU+ZGlyPFwvY29kZT4gXHViNjEwXHViMjk0IDxjb2RlPk1PVkU8XC9jb2RlPlx1YzY0MCA8Y29kZT5kPFwvY29kZT5cdWM3NTggXHVjMzBkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIDxjb2RlPmRpcjxcL2NvZGU+XHVjNzQwIDAgXHViNjEwXHViMjk0IDFcdWM3NzRcdWJhNzAgPGNvZGU+ZDxcL2NvZGU+XHViMjk0IDEsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWI4NWNcdWJkMDdcdWM3NTggXHVjYzk4XHVjNzRjIFx1YzcwNFx1Y2U1OFx1YjI5NCAoMCwgMClcdWM3NzRcdWJhNzAgXHViM2Q5XHVjYWJkXHVjNzQ0IFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWM3NGNcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3M2NcdWI4NWMgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJhODVcdWI4MzlcdWM1YjQgXHVjNWY0XHVjNzc0IFx1YzcyMFx1ZDZhOFx1ZDU1OFx1YjJlNFx1YmE3NCBcdWI0NTAgXHVjNzRjIFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YmE4NVx1YjgzOVx1YzViNCBcdWMyMThcdWQ1ODkgXHVkNmM0IFx1Yjg1Y1x1YmQwN1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NTggeFx1Yzg4Y1x1ZDQ1Y1x1YzY0MCB5XHVjODhjXHVkNDVjXHVjNzc0XHVhY2UwIFx1YmU0OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViYTg1XHViODM5XHVjNWI0IFx1YzVmNFx1Yzc3NCBcdWM3MjBcdWQ2YThcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMzU2NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvYm90IiwiZGVzY3JpcHRpb24iOiI8cD5BIHJvYm90IHJlY2VpdmVzIGEgc2VyaWVzIG9mIGluc3RydWN0aW9ucywgYW5kIG1vdmVzIGluIGEgc3F1YXJlIHJlZ2lvbiBTIGFsb25nIHRoZSBkaXJlY3Rpb24gcGFyYWxsZWwgdG8geC1heGlzIG9yIHktYXhpcyB0aGF0IHRoZSBpbnN0cnVjdGlvbnMgdGVsbC4gVGhlIGxvd2VyIGxlZnQgY29ybmVyIG9mIFMgaXMgKDAsIDApLCBhbmQgdGhlIHVwcGVyIHJpZ2h0IGNvcm5lciBvZiBTIGlzIChNLCBNKS4gSW5pdGlhbGx5LCB0aGUgcm9ib3QgaXMgbG9jYXRlZCBhdCAoMCwgMCksIGFuZCBoZWFkcyB0byB0aGUgZWFzdCBkaXJlY3Rpb24uPFwvcD5cclxuXHJcbjxwPkFuIGluc3RydWN0aW9uIGlzIGEgcGFpciBvZiBhY3Rpb24gYW5kIHZhbHVlLCB3aGVyZSB0aGUgYWN0aW9uIGlzIHRoZSB0eXBlIHRoYXQgdGhlIHJvYm90IGFjdHMgYXQgdGhlIGN1cnJlbnQgcm9ib3QgcG9zaXRpb24sIGFuZCB0aGUgdmFsdWUgaXMgYSBwYXJhbWV0ZXIgd2l0aCB3aGljaCB0aGUgcm9ib3QgYWN0cy4gVGhlcmUgYXJlIHR3byBhY3Rpb25zLCA8Y29kZT5UVVJOPFwvY29kZT4gYW5kIDxjb2RlPk1PVkU8XC9jb2RlPi4gVGhlIGluc3RydWN0aW9uIDxjb2RlPlRVUk4gMDxcL2NvZGU+IG1ha2VzIHRoZSByb2JvdCB0dXJuIDkwIGRlZ3JlZXMgdG8gdGhlIGxlZnQgYXQgaXRzIGN1cnJlbnQgcG9zaXRpb24sIGFuZCA8Y29kZT5UVVJOIDE8XC9jb2RlPiBtYWtlcyB0aGUgcm9ib3QgdHVybiA5MCBkZWdyZWVzIHRvIHRoZSByaWdodCBhdCBpdHMgY3VycmVudCBwb3NpdGlvbi4gVGhlIGluc3RydWN0aW9uIDxjb2RlPk1PVkUgZDxcL2NvZGU+IG1ha2VzIHRoZSByb2JvdCBtb3ZlIGQgdW5pdHMgdG8gdGhlIGRpcmVjdGlvbiB0aGUgcm9ib3QgY3VycmVudGx5IGhlYWRzLiBUaGUgZGlzdGFuY2UgZCBpcyBhIHBvc2l0aXZlIGludGVnZXIuPFwvcD5cclxuXHJcbjxwPkFuIGluc3RydWN0aW9uIGlzIHZhbGlkIGlmIHRoZSBwb3NpdGlvbiB0aGF0IHRoZSByb2JvdCBzdGF5cyBhZnRlciBleGVjdXRpbmcgdGhlIGluc3RydWN0aW9uIGlzIGluc2lkZSBvciBib3VuZGFyeSBvZiBTLiBJbiBvdGhlciB3b3JkcywgdGhlIGluc3RydWN0aW9uIGlzIG5vdCB2YWxpZCBpZiBpdCBtYWtlcyB0aGUgcm9ib3QgbGVhdmUgUyBjb21wbGV0ZWx5LiBBIHNlcmllcyBvZiB0aGUgaW5zdHJ1Y3Rpb25zIGlzIHZhbGlkIGlmIHRoZSBpbnN0cnVjdGlvbnMgYXJlIGFsbCB2YWxpZC48XC9wPlxyXG5cclxuPHA+V2Ugc3VwcG9zZSB0aGF0IGEgcm9ib3QgZ2V0cyBhIHNlcmllcyBvZiBpbnN0cnVjdGlvbnMsICg8Y29kZT5NT1ZFIDY8XC9jb2RlPiwgPGNvZGU+VFVSTiAwPFwvY29kZT4sIDxjb2RlPk1PVkUgNTxcL2NvZGU+LCA8Y29kZT5UVVJOIDA8XC9jb2RlPiwgPGNvZGU+TU9WRSAyPFwvY29kZT4sIDxjb2RlPlRVUk4gMDxcL2NvZGU+LCA8Y29kZT5NT1ZFIDI8XC9jb2RlPiwgPGNvZGU+VFVSTiAwPFwvY29kZT4sIDxjb2RlPk1PVkUgNDxcL2NvZGU+LCA8Y29kZT5UVVJOIDA8XC9jb2RlPiwgPGNvZGU+TU9WRSAzPFwvY29kZT4sIDxjb2RlPk1PVkUgMjxcL2NvZGU+KSBhcyBpbiB0aGUgbGVmdCBmaWd1cmUgYmVsb3csIHRoZW4gaXQgZmluYWxseSByZWFjaGVzIGF0ICg4LCA4KS4gRm9yIGFub3RoZXIgc2VyaWVzIG9mIHRoZSBpbnN0cnVjdGlvbnMsICg8Y29kZT5NT1ZFIDEwPFwvY29kZT4sIDxjb2RlPlRVUk4gMDxcL2NvZGU+LCA8Y29kZT5NT1ZFIDI8XC9jb2RlPiwgPGNvZGU+VFVSTiAwPFwvY29kZT4sIDxjb2RlPk1PVkUgNTxcL2NvZGU+LCA8Y29kZT5UVVJOIDE8XC9jb2RlPiwgPGNvZGU+TU9WRSA1PFwvY29kZT4sIDxjb2RlPlRVUk4gMTxcL2NvZGU+LCA8Y29kZT5NT1ZFIDI8XC9jb2RlPiwgPGNvZGU+VFVSTiAxPFwvY29kZT4sIDxjb2RlPk1PVkUgMzxcL2NvZGU+LCA8Y29kZT5UVVJOIDA8XC9jb2RlPiwgPGNvZGU+VFVSTiAwPFwvY29kZT4sIDxjb2RlPk1PVkUgNjxcL2NvZGU+KSBpbiB0aGUgbWlkZGxlIGZpZ3VyZSwgdGhlIHJvYm90IHdpbGwgYmUgYXQgKDcsIDEwKS4gSG93ZXZlciwgdGhlIGZpbmFsIHNlcmllcyBvZiB0aGUgaW5zdHJ1Y3Rpb25zLCAoPGNvZGU+TU9WRSA1PFwvY29kZT4sIDxjb2RlPlRVUk4gMDxcL2NvZGU+LCA8Y29kZT5NT1ZFIDQ8XC9jb2RlPiwgPGNvZGU+VFVSTiAxPFwvY29kZT4sIDxjb2RlPk1PVkUgMjxcL2NvZGU+LCA8Y29kZT5UVVJOIDE8XC9jb2RlPiwgPGNvZGU+TU9WRSA1PFwvY29kZT4pIGluIHRoZSByaWdodCBmaWd1cmUsIG1ha2VzIHRoZSByb2JvdCBtb3ZlIG91dCBvZiBTLCBpLmUuLCBlbnRlciB0aGUgZXh0ZXJpb3Igb2YgUywgc28gdGhpcyBzZXJpZXMgaXMgbm90IHZhbGlkLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMzU2N1wvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjhweDsgd2lkdGg6NjM4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuIFRocmVlIHJvdXRlcyBvZiB0aGUgcm9ib3QgZm9yIHRocmVlIGRpZmZlcmVudCBzZXJpZXMgb2YgaW5zdHJ1Y3Rpb25zIHdoZXJlIE0gPSAxMS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBzaWRlIGxlbmd0aCBNIG9mIGEgc3F1YXJlLCBhIHNlcmllcyBvZiBuICgmZ2U7IDEpIGluc3RydWN0aW9ucywgYW5kIGEgcm9ib3QgYXQgYW4gaW5pdGlhbCBwb3NpdGlvbiAoMCwgMCkgb2YgUyBoZWFkaW5nIHRvIHRoZSBlYXN0LCB3cml0ZSBhIHByb2dyYW0gdG8gb3V0cHV0IHRoZSBmaW5hbCBwb3NpdGlvbiB0aGUgcm9ib3QgcmVhY2hlcyBhZnRlciBleGVjdXRpbmcgbiBpbnN0cnVjdGlvbnMgb25lIGJ5IG9uZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMsIE0gYW5kIG4gKDEgJmxlOyBNICZsZTsgMSwwMDAsIDEgJmxlOyBuICZsZTsgMSwwMDApLCB3aGVyZSBNIGlzIHRoZSBzaWRlIGxlbmd0aCBvZiB0aGUgc3F1YXJlIFMsIGkuZS4sIGl0cyB1cHBlciByaWdodCBjb3JuZXIgaGFzIGNvb3JkaW5hdGVzICh4LCB5KSA9IChNLCBNKSwgYW5kIG4gaXMgdGhlIG51bWJlciBvZiBpbnN0cnVjdGlvbnMgdGhlIHJvYm90IHdpbGwgZXhlY3V0ZS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgaW5zdHJ1Y3Rpb24uIEVhY2ggaW5zdHJ1Y3Rpb24gaXMgcmVwcmVzZW50ZWQgYnkgYSBwYWlyIG9mIDxjb2RlPlRVUk48XC9jb2RlPiBhbmQgPGNvZGU+ZGlyPFwvY29kZT4gb3IgYnkgYSBwYWlyIG9mIDxjb2RlPk1PVkU8XC9jb2RlPiBhbmQgPGNvZGU+ZDxcL2NvZGU+LCB3aGVyZSA8Y29kZT5kaXI8XC9jb2RlPiBpcyAwIG9yIDEgYW5kIDxjb2RlPmQ8XC9jb2RlPiBpcyBhIHBvc2l0aXZlIGludGVnZXIgbm8gbW9yZSB0aGFuIDEsMDAwLiBOb3RlIHRoYXQgdGhlIHJvYm90IGlzIGluaXRpYWxseSBhdCAoMCwgMCkgb2YgUyBhbmQgaGVhZHMgdG8gdGhlIGVhc3QgZGlyZWN0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUuIElmIHRoZSBzZXJpZXMgb2YgdGhlIGluc3RydWN0aW9ucyBnaXZlbiBpbiB0aGUgaW5wdXQgaXMgdmFsaWQsIHRoZSBsaW5lIHNob3VsZCBjb250YWluIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMsIHdoaWNoIGFyZSB4LWNvb3JkaW5hdGUgYW5kIHktY29vcmRpbmF0ZSwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIG9mIHRoZSBwb3NpdGlvbiB0aGF0IHRoZSByb2JvdCByZWFjaGVzIGp1c3QgYWZ0ZXIgZXhlY3V0aW5nIGFsbCB0aGUgaW5zdHJ1Y3Rpb25zLiBJZiB0aGUgc2VyaWVzIGlzIG5vdCB2YWxpZCwgdGhlbiB0aGUgbGluZSBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIC0xLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2016 I번