시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2761 833 562 30.053%

문제

개미 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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIE5cdWI5YzhcdWI5YWMgXHVhYzFjXHViYmY4IFx1YzkxMVx1YzVkMFx1YzExYyBrXHViYzg4XHVjOWY4XHViODVjIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjMWNcdWJiZjhcdWM3NTggSURcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMWNcdWJiZjhcdWM3NTggSURcdWFjMDAgXHVjNTkxXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCArXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGYWxsaW5nIEFudHMiLCJkZXNjcmlwdGlvbiI6IjxwPk4gYW50cyBhcmUgb24gYSBzdGljayB3aGVyZSBzb21lIGZhY2luZyByaWdodCBhbmQgc29tZSBmYWNpbmcgbGVmdC4gWW91IGNhbiBhc3N1bWUgYWxsIGFudHMgYXJlIHNvIHRpbnkgY29tcGFyZWQgdG8gdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlbSwgdGhhdCB0aGV5IGNhbiBiZSBjb25zaWRlcmVkIG1vdmluZyBwb2ludHMgd2l0aG91dCB2b2x1bWUuIEZyb20gYSBzdGFydCBzaWduYWwsIGFsbCBhbnRzIGJlZ2luIHRvIG1hcmNoIGluIHdoaWNoZXZlciBkaXJlY3Rpb24gdGhleSBhcmUgY3VycmVudGx5IGZhY2luZy4gQWxsIGFudHMgbWFyY2ggaW4gYSBjb25zdGFudCBzcGVlZCBzdWNoIGFzIDFtbSBwZXIgc2Vjb25kLiBJZiB0d28gZGlmZmVyZW50IGFudHMgY29sbGlkZSBvbiBhIHBvaW50LCB0aGVuIHRoZXkgYm91bmNlIGFuZCByZXZlcnNlIHRoZWlyIHByZXZpb3VzIGRpcmVjdGlvbi4gQm91bmNpbmcgYW5kIHJldmVyc2luZyBtb3ZlbWVudCBkb2VzIG5vdCB0YWtlIGFueSB0aW1lLiBXaGVuIGFuIGFudCBpcyByZWFjaGluZyB0aGUgZW5kIG9mIHN0aWNrLCB0aGF0IGFudCBmYWxscyBvZmYgZnJvbSB0aGUgc3RpY2sgYW5kIGRvd24gdG8gdGhlIGdyb3VuZC4gV2UgYXNzdW1lIHRoZSBzdGljayBpcyBmbG9hdGluZyBvdmVyIGEgZmxvb3IuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluaXRpYWxseSBhbGwgYW50cyBhcmUgcGxhY2VkIGluIGRpc3RpbmN0IHBvc2l0aW9ucywgdGhhdCBtZWFucyBubyB0d28gYW50cyBhcmUgcGxhY2VkIGF0IGEgc2FtZSBwb2ludCBvZiB0aGUgc3RpY2suIFdlIHJlcHJlc2VudCBlYWNoIGFudCB1c2luZyBhIHNpZ25lZCBpbnRlZ2VyLCBjYWxsZWQgYW4gYW50IElELiBUaGUgc2lnbiBvZiB0aGUgYW50IElEIGRlbm90ZXMgdGhlIGZhY2luZyBkaXJlY3Rpb24gaW4gdGhlIGludGlhbCBzdGF0ZSwgd2hlcmUgJiMzOTstJiMzOTsoJiMzOTsrJiMzOTspIG1lYW5zIGZhY2luZyB0aGUgbGVmdCAocmlnaHQpLiBUaGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIGFudCBJRCBpcyBvbmUgb2YgTiBpbnRlZ2VycyAxLCAyLCBcdTIyZWYgLCBOLiBTbyB0aGUgYWJzb2x1dGUgdmFsdWVzIG9mIHRoZSBhbnQgSUQgYXJlIGFsbCBkaXN0aW5jdC4gSW4gRmlndXJlIDEsIHlvdSBjYW4gc2VlIHRoYXQgdGhlcmUgYXJlIDYgYW50cyB3aXRoIHRoZSBzaWduZWQgSUQgeys0LCArNSwgLTEsIC0zLCAtMiwgKzZ9IHdob3NlIGNvcnJlc3BvbmRpbmcgcG9zaXRpb25zIGFyZSAmbmJzcDt7NSw4LDE5LDIyLDI0LDI1fSBvbiBhIGxvbmcgc3RpY2sgd2l0aCBsZW5ndGggTCA9IDMwLiBUaGUgYXJyb3cgYXNzaWduZWQgZm9yIGVhY2ggYW50IHNob3dzIHRoZSBmYWNpbmcgZGlyZWN0aW9uIGluIHRoZSBpbml0aWFsIHN0YXRlLiBUaGUgcG9zaXRpb24gb2YgdGhlIGxlZnQgZW5kIGlzIDAsIGFuZCB0aGUgcG9zaXRpb24gb2YgdGhlIHJpZ2h0IGVuZCBpcyAzMC4gSXQgaXMgZWFzeSB0byBzZWUgdGhhdCB0aGUgYW50IG9mIElEICs2IHdpbGwgYXJyaXZlIGF0IHRoZSByaWdodCBlbmQgb2YgdGhlIHN0aWNrIGF0IHRpbWUgdCA9IDUsIGFuZCB0aGVuIGl0IGZhbGxzIG9mZiB0aGUgc3RpY2sgYXQgdCA9Ni4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9hbnQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NjQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBpbmZvcm1hdGlvbiBvZiBhbnRzIGJlZm9yZSBtYXJjaGluZzsgYW50IElEIGFuZCB0aGUgY29ycmVzcG9uZGluZyBwb3NpdGlvbiBvbiBhIHN0aWNrLiBJZiB0d28gYW50cyBhcmUgZmFsbGluZyBzaW11bHRhbmVvdXNseSBmcm9tIGJvdGggc2lkZXMgKGxlZnQgYW5kIHJpZ2h0KSwgdGhlbiB3ZSB3aWxsIGJyZWFrIHRoZSB0aWUgb2YgZmFsbGluZyBvcmRlciBzdWNoIHRoYXQgdGhlIGFudCB3aXRoIHNtYWxsZXIgSUQgbnVtYmVyIGZhbGxzIG9mZiBzbGlnaHRseSBlYXJsaWVyIHRoYW4gdGhlIG90aGVyLiBMZXQgdXMgZ2l2ZSBvbmUgZXhhbXBsZSBmb3IgdGhpcyBjYXNlLiBJbiBGaWd1cmUgMiwgaWYgdHdvIGFudHMgd2l0aCBJRCA9IHstMSwgKzJ9IHdpbGwgcmVhY2ggZWFjaCBlbmQgc2ltdWx0YW5lb3VzbHksIHRoZSBhbnQgb2YgSUQgPSAtMSB3aWxsIGZhbGwgb2ZmIGVhcmxpZXIgdGhhbiB0aGUgYW50IG9mIElEID0gKzIgc2luY2UgLTEgJmx0OyArMi4gU28gdGhlIGZhbGxpbmcgc2VxdWVuY2Ugb2YgZm91ciBhbnRzIGluIEZpZ3VyZSAyIGlzIFx1MzAwOC0xLCAyLCA0LCAzXHUzMDA5LCBpLmUuLCB0aGUgYW50IG9mIElEID0gLTEgZmFsbHMgb2ZmIHRoZSBmaXJzdCBhbmQgdGhlIGFudCBvZiBJRCA9IDMgZmFsbHMgb2ZmIHRoZSBsYXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FudDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo1MzlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHBvc2l0aXZlIGludGVnZXIgMSAmbGU7IGsgJmxlOyBuLCB5b3Ugc2hvdWxkIGZpbmQgdGhlIGstdGggYW50IGluIHRoZSBmYWxsaW5nIHNlcXVlbmNlLCBpLmUuLCB0aGUgay10aCBmYWxsaW5nIGFudC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggdGhyZWUgaW50ZWdlciBudW1iZXJzIE4sIEwgYW5kIGssIHdoZXJlIE4gaXMgdGhlIHRvdGFsIG51bWJlciBvZiB0aGUgYW50cywgTCBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzdGljaywgYW5kIGsgaXMgdGhlIGZhbGxpbmcgb3JkZXIgd2UgYXJlIGNvbmNlcm5lZCB3aXRoIGsgJmxlOyBOLiBFYWNoIGxpbmUgaW4gdGhlIGZvbGxvd2luZyBoYXMgdHdvIGludGVnZXIgbnVtYmVycywgcDxzdWI+aTxcL3N1Yj4gYW5kIGE8c3ViPmk8XC9zdWI+LCB3aGVyZSBwPHN1Yj5pPFwvc3ViPiBpcyB0aGUgaW5pdGlhbCBwb3NpdGlvbiBvZiB0aGUgYW50IGE8c3ViPmk8XC9zdWI+LiBOb3RlIHRoYXQgcDxzdWI+aTxcL3N1Yj4gaXMgaW5jcmVhc2luZyBzdWNoIGFzIHA8c3ViPmk8XC9zdWI+ICZsdDsgcDxzdWI+aSsxPFwvc3ViPiAuIE5vdGUgdGhhdCAxICZsZTsgcDxzdWI+aTxcL3N1Yj4gJmxlOyBMIC0gMSwgMyAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxMCAmbGU7IEwgJmxlOyA1LDAwMCwwMDAgYW5kIDEgJmxlOyBrICZsZTsgTi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIElEIG51bWJlciBvZiB0aGUgay10aCBmYWxsaW5nIGFudCBmcm9tIHRoZSBzdGljayBhbW9uZyBhbGwgTiBhbnRzLiBZb3Ugc2hvdWxkIG5vdCB3cml0ZSAmbHNxdW87KyZyc3F1bzsgc3ltYm9sIGlmIHRoZSBhbnQgSUQgaXMgcG9zaXRpdmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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