시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2089 633 433 30.111%

문제

개미 N마리가 막대 위에 올라가 있다. 일부 개미는 왼쪽을 바라보고 있고, 나머지 개미는 오른쪽을 바라보고 있다. 모든 개미는 매우 작아서 크기가 없는 점으로 나타낼 수 있다. 시작 신호가 주어지면, 개미는 바라보고 있는 방향으로 행진을 시작한다. 모든 개미는 동일한 속도 초속 1mm로 이동한다. 두 개미가 한 점에서 충돌하는 경우가 발생할 수 있다. 이 경우에 두 개미는 행진하는 방향을 반대 방향으로 바꾸고, 행진을 계속하게 된다. 개미가 방향을 바꾸는데 걸리는 시간은 없다. 개미가 막대의 끝에 도착하는 경우에는, 막대에서 떨어지게 된다. 막대는 땅 위에 떠있다고 가정한다.

처음에 모든 개미의 위치는 서로 다르다. 즉, 두 개미가 막대 위의 한 점에 같이 있는 경우는 없다. 개미는 부호 있는 정수로 나타낼 수 있다. 이 정수를 개미의 ID라고 한다. 개미의 ID의 부호는 개미가 처음에 바라보고 있는 방향이다. -는 왼쪽을 바라보고 있는 것이고, +는 오른쪽을 바라보고 있는 것이다. 개미의 ID의 절댓값은 1부터 109까지의 정수 중 하나이다. 또, 모든 개미의 ID의 절댓값은 서로 다르다. 아래 그림에는 개미가 총 6마리가 있고, ID는 {+4, +5, -1, -3, -2, +6}이다. 각 개미의 초기 위치는 {5, 8, 19, 22, 24, 25}이며, 막대의 길이 L = 30이다. 화살표는 처음에 개미가 바라보고 있는 방향을 나타낸다. 왼쪽 끝의 좌표는 0이고, 오른쪽 끝의 좌표는 30이다. ID가 +6인 개미는 시간 t = 5일 때, 막대의 오른쪽 끝에 도착하며, t = 6에 막대에서 떨어지게 된다.

개미가 행진을 시작하기 전의 상태 (ID와 막대 상의 위치)가 주어진다. 두 개미가 동시에 막대의 양 끝에서 떨어지는 경우에는, ID가 작은 개미가 조금 더 먼저 떨어진다고 한다. 아래 그림은 이와 같은 경우를 나타낸 그림이다. 두 개미 {-1, +2}는 끝에 동시에 도착하게 된다. -1 < +2 이기 때문에, ID가 -1인 개미가 +2인 개미보다 조금 더 먼저 떨어지게 된다. 따라서, 아래 그림의 네 개미가 떨어지는 순서는 {-1, 2, 4, 3}이 된다.

양의 정수 1 ≤ k ≤ n이 주어졌을 때, k번째로 떨어지는 개미를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, L, k가 주어진다. 다음 N개 줄에는 pi와 ai가 주어진다. ai는 개미의 ID이고, pi는 그 개미의 초기 위치이다. 항상 pi가 증가하는 순서로 (pi<pi+1) 주어진다. (1 ≤ pi ≤ L-1, 3 ≤ N ≤ 100,000, 10 ≤ L ≤ 5,000,000, 1 ≤ k ≤ N)

출력

각 테스트 케이스마다, N마리 개미 중에서 k번째로 떨어지는 개미의 ID를 출력한다. 개미의 ID가 양수인 경우에 +를 출력하면 안된다.

예제 입력 1

2
6 30 3
5 4
8 5
19 -1
22 -3
24 -2
25 6
4 35 2
5 -1
12 3
20 4
30 2

예제 출력 1

-2
2
W3sicHJvYmxlbV9pZCI6IjMxNjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzFjXHViYmY4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMWNcdWJiZjggTlx1YjljOFx1YjlhY1x1YWMwMCBcdWI5YzlcdWIzMDAgXHVjNzA0XHVjNWQwIFx1YzYyY1x1Yjc3Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3Y1x1YmQ4MCBcdWFjMWNcdWJiZjhcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNzQ0IFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFjMWNcdWJiZjhcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQ0IFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFjMWNcdWJiZjhcdWIyOTQgXHViOWU0XHVjNmIwIFx1Yzc5MVx1YzU0NFx1YzExYyBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjNWM2XHViMjk0IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMmRjXHVjNzkxIFx1YzJlMFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YWMxY1x1YmJmOFx1YjI5NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQ1ODlcdWM5YzRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhYzFjXHViYmY4XHViMjk0IFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWMxOGRcdWIzYzQgXHVjZDA4XHVjMThkIDFtbVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVkNTVjIFx1YzgxMFx1YzVkMFx1YzExYyBcdWNkYTlcdWIzY2NcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjQ1MCBcdWFjMWNcdWJiZjhcdWIyOTQgXHVkNTg5XHVjOWM0XHVkNTU4XHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmMxNFx1YWZiOFx1YWNlMCwgXHVkNTg5XHVjOWM0XHVjNzQ0IFx1YWNjNFx1YzE4ZFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHVjNWM2XHViMmU0LiBcdWFjMWNcdWJiZjhcdWFjMDAgXHViOWM5XHViMzAwXHVjNzU4IFx1YjA1ZFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWI5YzlcdWIzMDBcdWM1ZDBcdWMxMWMgXHViNWE4XHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViOWM5XHViMzAwXHViMjk0IFx1YjU0NSBcdWM3MDRcdWM1ZDAgXHViNWEwXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzk4XHVjNzRjXHVjNWQwIFx1YmFhOFx1YjRlMCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1Yzk4OSwgXHViNDUwIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWI5YzlcdWIzMDAgXHVjNzA0XHVjNzU4IFx1ZDU1YyBcdWM4MTBcdWM1ZDAgXHVhYzE5XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWFjMWNcdWJiZjhcdWIyOTQgXHViZDgwXHVkNjM4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWI5N2MgXHVhYzFjXHViYmY4XHVjNzU4IElEXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzFjXHViYmY4XHVjNzU4IElEXHVjNzU4IFx1YmQ4MFx1ZDYzOFx1YjI5NCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0XHViMmU0LiAtXHViMjk0IFx1YzY3Y1x1Y2FiZFx1Yzc0NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgK1x1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWMxY1x1YmJmOFx1Yzc1OCBJRFx1Yzc1OCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NDAgMVx1YmQ4MFx1ZDEzMCAxMDxzdXA+OTxcL3N1cD5cdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVjMjE4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHViYWE4XHViNGUwIFx1YWMxY1x1YmJmOFx1Yzc1OCBJRFx1Yzc1OCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YjI5NCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVjZDFkIDZcdWI5YzhcdWI5YWNcdWFjMDAgXHVjNzg4XHVhY2UwLCBJRFx1YjI5NCB7KzQsICs1LCAtMSwgLTMsIC0yLCArNn1cdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWFjMWNcdWJiZjhcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzcwNFx1Y2U1OFx1YjI5NCB7NSwgOCwgMTksIDIyLCAyNCwgMjV9XHVjNzc0XHViYTcwLCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZTM4XHVjNzc0IEwgPSAzMFx1Yzc3NFx1YjJlNC4gXHVkNjU0XHVjMGI0XHVkNDVjXHViMjk0IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWFjMWNcdWJiZjhcdWFjMDAgXHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM2N2NcdWNhYmQgXHViMDVkXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAwXHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMDVkXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAzMFx1Yzc3NFx1YjJlNC4gSURcdWFjMDAgKzZcdWM3NzggXHVhYzFjXHViYmY4XHViMjk0IFx1YzJkY1x1YWMwNCB0ID0gNVx1Yzc3YyBcdWI1NGMsIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMDVkXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3MCwgdCA9IDZcdWM1ZDAgXHViOWM5XHViMzAwXHVjNWQwXHVjMTFjIFx1YjVhOFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYW50MSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODRweDsgd2lkdGg6NjQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzFjXHViYmY4XHVhYzAwIFx1ZDU4OVx1YzljNFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0XHVjNzU4IFx1YzBjMVx1ZDBkYyAoSURcdWM2NDAgXHViOWM5XHViMzAwIFx1YzBjMVx1Yzc1OCBcdWM3MDRcdWNlNTgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViOWM5XHViMzAwXHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM1ZDBcdWMxMWMgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgSURcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWM4NzBcdWFlMDggXHViMzU0IFx1YmEzY1x1YzgwMCZuYnNwO1x1YjVhOFx1YzViNFx1YzljNFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YWMxY1x1YmJmOCB7LTEsICsyfVx1YjI5NCBcdWIwNWRcdWM1ZDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIC0xICZsdDsgKzIgXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgSURcdWFjMDAgLTFcdWM3NzggXHVhYzFjXHViYmY4XHVhYzAwICsyXHVjNzc4IFx1YWMxY1x1YmJmOFx1YmNmNFx1YjJlNCBcdWM4NzBcdWFlMDggXHViMzU0IFx1YmEzY1x1YzgwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NTggXHViMTI0IFx1YWMxY1x1YmJmOFx1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IHstMSwgMiwgNCwgM31cdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FudDIoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjUzOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggMSAmbGU7IGsgJmxlOyBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIGtcdWJjODhcdWM5ZjhcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWMxY1x1YmJmOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTiwgTCwga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBwPHN1Yj5pPFwvc3ViPlx1YzY0MCZuYnNwO2E8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gYTxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVhYzFjXHViYmY4XHVjNzU4IElEXHVjNzc0XHVhY2UwLCBwPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWFkZjggXHVhYzFjXHViYmY4XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWM3MDRcdWNlNThcdWM3NzRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBwPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIChwPHN1Yj5pPFwvc3ViPiZsdDtwPHN1Yj5pKzE8XC9zdWI+KSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgcDxzdWI+aTxcL3N1Yj4gJmxlOyBMLTEsIDMgJmxlOyBOICZsZTsgMTAwLDAwMCwgMTAgJmxlOyBMICZsZTsgNSwwMDAsMDAwLCAxICZsZTsgayAmbGU7IE4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIE5cdWI5YzhcdWI5YWMgXHVhYzFjXHViYmY4IFx1YzkxMVx1YzVkMFx1YzExYyBrXHViYzg4XHVjOWY4XHViODVjIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjMWNcdWJiZjhcdWM3NTggSURcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMWNcdWJiZjhcdWM3NTggSURcdWFjMDAgXHVjNTkxXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCArXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhbGxpbmcgQW50cyIsImRlc2NyaXB0aW9uIjoiPHA+TiBhbnRzIGFyZSBvbiBhIHN0aWNrIHdoZXJlIHNvbWUgZmFjaW5nIHJpZ2h0IGFuZCBzb21lIGZhY2luZyBsZWZ0LiBZb3UgY2FuIGFzc3VtZSBhbGwgYW50cyBhcmUgc28gdGlueSBjb21wYXJlZCB0byB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGVtLCB0aGF0IHRoZXkgY2FuIGJlIGNvbnNpZGVyZWQgbW92aW5nIHBvaW50cyB3aXRob3V0IHZvbHVtZS4gRnJvbSBhIHN0YXJ0IHNpZ25hbCwgYWxsIGFudHMgYmVnaW4gdG8gbWFyY2ggaW4gd2hpY2hldmVyIGRpcmVjdGlvbiB0aGV5IGFyZSBjdXJyZW50bHkgZmFjaW5nLiBBbGwgYW50cyBtYXJjaCBpbiBhIGNvbnN0YW50IHNwZWVkIHN1Y2ggYXMgMW1tIHBlciBzZWNvbmQuIElmIHR3byBkaWZmZXJlbnQgYW50cyBjb2xsaWRlIG9uIGEgcG9pbnQsIHRoZW4gdGhleSBib3VuY2UgYW5kIHJldmVyc2UgdGhlaXIgcHJldmlvdXMgZGlyZWN0aW9uLiBCb3VuY2luZyBhbmQgcmV2ZXJzaW5nIG1vdmVtZW50IGRvZXMgbm90IHRha2UgYW55IHRpbWUuIFdoZW4gYW4gYW50IGlzIHJlYWNoaW5nIHRoZSBlbmQgb2Ygc3RpY2ssIHRoYXQgYW50IGZhbGxzIG9mZiBmcm9tIHRoZSBzdGljayBhbmQgZG93biB0byB0aGUgZ3JvdW5kLiBXZSBhc3N1bWUgdGhlIHN0aWNrIGlzIGZsb2F0aW5nIG92ZXIgYSBmbG9vci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5IGFsbCBhbnRzIGFyZSBwbGFjZWQgaW4gZGlzdGluY3QgcG9zaXRpb25zLCB0aGF0IG1lYW5zIG5vIHR3byBhbnRzIGFyZSBwbGFjZWQgYXQgYSBzYW1lIHBvaW50IG9mIHRoZSBzdGljay4gV2UgcmVwcmVzZW50IGVhY2ggYW50IHVzaW5nIGEgc2lnbmVkIGludGVnZXIsIGNhbGxlZCBhbiBhbnQgSUQuIFRoZSBzaWduIG9mIHRoZSBhbnQgSUQgZGVub3RlcyB0aGUgZmFjaW5nIGRpcmVjdGlvbiBpbiB0aGUgaW50aWFsIHN0YXRlLCB3aGVyZSAmIzM5Oy0mIzM5OygmIzM5OysmIzM5OykgbWVhbnMgZmFjaW5nIHRoZSBsZWZ0IChyaWdodCkuIFRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiB0aGUgYW50IElEIGlzIG9uZSBvZiBOIGludGVnZXJzIDEsIDIsIFx1MjJlZiAsIE4uIFNvIHRoZSBhYnNvbHV0ZSB2YWx1ZXMgb2YgdGhlIGFudCBJRCBhcmUgYWxsIGRpc3RpbmN0LiBJbiBGaWd1cmUgMSwgeW91IGNhbiBzZWUgdGhhdCB0aGVyZSBhcmUgNiBhbnRzIHdpdGggdGhlIHNpZ25lZCBJRCB7KzQsICs1LCAtMSwgLTMsIC0yLCArNn0gd2hvc2UgY29ycmVzcG9uZGluZyBwb3NpdGlvbnMgYXJlICZuYnNwO3s1LDgsMTksMjIsMjQsMjV9IG9uIGEgbG9uZyBzdGljayB3aXRoIGxlbmd0aCBMID0gMzAuIFRoZSBhcnJvdyBhc3NpZ25lZCBmb3IgZWFjaCBhbnQgc2hvd3MgdGhlIGZhY2luZyBkaXJlY3Rpb24gaW4gdGhlIGluaXRpYWwgc3RhdGUuIFRoZSBwb3NpdGlvbiBvZiB0aGUgbGVmdCBlbmQgaXMgMCwgYW5kIHRoZSBwb3NpdGlvbiBvZiB0aGUgcmlnaHQgZW5kIGlzIDMwLiBJdCBpcyBlYXN5IHRvIHNlZSB0aGF0IHRoZSBhbnQgb2YgSUQgKzYgd2lsbCBhcnJpdmUgYXQgdGhlIHJpZ2h0IGVuZCBvZiB0aGUgc3RpY2sgYXQgdGltZSB0ID0gNSwgYW5kIHRoZW4gaXQgZmFsbHMgb2ZmIHRoZSBzdGljayBhdCB0ID02LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FudDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg0cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo2NDZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIGluZm9ybWF0aW9uIG9mIGFudHMgYmVmb3JlIG1hcmNoaW5nOyBhbnQgSUQgYW5kIHRoZSBjb3JyZXNwb25kaW5nIHBvc2l0aW9uIG9uIGEgc3RpY2suIElmIHR3byBhbnRzIGFyZSBmYWxsaW5nIHNpbXVsdGFuZW91c2x5IGZyb20gYm90aCBzaWRlcyAobGVmdCBhbmQgcmlnaHQpLCB0aGVuIHdlIHdpbGwgYnJlYWsgdGhlIHRpZSBvZiBmYWxsaW5nIG9yZGVyIHN1Y2ggdGhhdCB0aGUgYW50IHdpdGggc21hbGxlciBJRCBudW1iZXIgZmFsbHMgb2ZmIHNsaWdodGx5IGVhcmxpZXIgdGhhbiB0aGUgb3RoZXIuIExldCB1cyBnaXZlIG9uZSBleGFtcGxlIGZvciB0aGlzIGNhc2UuIEluIEZpZ3VyZSAyLCBpZiB0d28gYW50cyB3aXRoIElEID0gey0xLCArMn0gd2lsbCByZWFjaCBlYWNoIGVuZCBzaW11bHRhbmVvdXNseSwgdGhlIGFudCBvZiBJRCA9IC0xIHdpbGwgZmFsbCBvZmYgZWFybGllciB0aGFuIHRoZSBhbnQgb2YgSUQgPSArMiBzaW5jZSAtMSAmbHQ7ICsyLiBTbyB0aGUgZmFsbGluZyBzZXF1ZW5jZSBvZiBmb3VyIGFudHMgaW4gRmlndXJlIDIgaXMgXHUzMDA4LTEsIDIsIDQsIDNcdTMwMDksIGkuZS4sIHRoZSBhbnQgb2YgSUQgPSAtMSBmYWxscyBvZmYgdGhlIGZpcnN0IGFuZCB0aGUgYW50IG9mIElEID0gMyBmYWxscyBvZmYgdGhlIGxhc3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYW50Mi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTZweDsgb3BhY2l0eTowLjk7IHdpZHRoOjUzOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciAxICZsZTsgayAmbGU7IG4sIHlvdSBzaG91bGQgZmluZCB0aGUgay10aCBhbnQgaW4gdGhlIGZhbGxpbmcgc2VxdWVuY2UsIGkuZS4sIHRoZSBrLXRoIGZhbGxpbmcgYW50LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCB0aHJlZSBpbnRlZ2VyIG51bWJlcnMgTiwgTCBhbmQgaywgd2hlcmUgTiBpcyB0aGUgdG90YWwgbnVtYmVyIG9mIHRoZSBhbnRzLCBMIGlzIHRoZSBsZW5ndGggb2YgdGhlIHN0aWNrLCBhbmQgayBpcyB0aGUgZmFsbGluZyBvcmRlciB3ZSBhcmUgY29uY2VybmVkIHdpdGggayAmbGU7IE4uIEVhY2ggbGluZSBpbiB0aGUgZm9sbG93aW5nIGhhcyB0d28gaW50ZWdlciBudW1iZXJzLCBwPHN1Yj5pPFwvc3ViPiBhbmQgYTxzdWI+aTxcL3N1Yj4sIHdoZXJlIHA8c3ViPmk8XC9zdWI+IGlzIHRoZSBpbml0aWFsIHBvc2l0aW9uIG9mIHRoZSBhbnQgYTxzdWI+aTxcL3N1Yj4uIE5vdGUgdGhhdCBwPHN1Yj5pPFwvc3ViPiBpcyBpbmNyZWFzaW5nIHN1Y2ggYXMgcDxzdWI+aTxcL3N1Yj4gJmx0OyBwPHN1Yj5pKzE8XC9zdWI+IC4gTm90ZSB0aGF0IDEgJmxlOyBwPHN1Yj5pPFwvc3ViPiAmbGU7IEwgLSAxLCAzICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEwICZsZTsgTCAmbGU7IDUsMDAwLDAwMCBhbmQgMSAmbGU7IGsgJmxlOyBOLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgSUQgbnVtYmVyIG9mIHRoZSBrLXRoIGZhbGxpbmcgYW50IGZyb20gdGhlIHN0aWNrIGFtb25nIGFsbCBOIGFudHMuIFlvdSBzaG91bGQgbm90IHdyaXRlICZsc3F1bzsrJnJzcXVvOyBzeW1ib2wgaWYgdGhlIGFudCBJRCBpcyBwb3NpdGl2ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 E번