시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 256 MB 1409 202 113 21.984%

문제

홍준이는 대한민국의 자랑스러운 해군이다. 오늘은 전함을 타고 적과 싸우는 상황을 가정한 실전 연습을 하려고 한다. 

전장은 n × n 크기의 그리드로 나타낼 수 있다. 가장 왼쪽 아래 점의 좌표는 (1,1)이고, 가장 오른쪽 위 점의 좌표는 (n,n)이다. 적의 함대는 전함 k개로 이루어져 있다. 각 전함 i는 길이가 0보다 크고 양 끝점이 (xi,yi), (x'i,y'i)인 선분으로 나타낼 수 있다. 또, 전함의 무게는 wi이다. 홍준이는 전함을 부수기 위해 레이저 대포를 총 l번 발사한다. 대포는 수직이나 수평 방향으로 발사할 수 있다.

대포를 수직으로 발사한다면, 레이저는 (a,1)과 (a,n)을 연결하는 선분으로 나타낼 수 있고, 이 선분과 만나는 전함을 모두 파괴한다. (끝점도 포함) 대포를 수평으로 발사하면, 레이저는 (1,a)와 (n,a)를 연결하는 선분으로 나타낼 수 있고, 이 선분과 만나는 전함도 모두 파괴한다.

홍준이는 매번 레이저 캐논을 발사할 때마다, 파괴한 전함중 가장 무거운 전함을 대통령에게 보고해야 한다.

아래 그림에는 5 × 5 크기의 그리드에 전함이 다섯 개 있다. 각 전함의 무게는 선분 옆에 쓰여 있다. 첫 번째 레이저를 (4,1)과 (4,5)를 연결하는 선분으로 수직 발사하면, 전함 두 개를 파괴할 수 있다. 파괴한 전함의 무게는 4와 5인데, 가장 무거운 전함은 5이므로 5를 보고한다. 그 다음, 레이저를 (1,4)와 (5,4)를 연결하는 선분으로 수평 발사하면, 두 전함을 파괴할 수 있다. 파괴한 전함의 무게는 1과 2이고, 무거운 전함은 2이므로 2를 보고한다. 두 번째 레이저를 발사했을 때, 무게가 4인 전함은 첫 번째 레이저에 의해서 파괴되었기 때문에 파괴되지 않는다.

모든 전함의 위치와 홍준이가 발사한 레이저의 정보가 주어진다. 레이저를 발사할 때마다, 파괴한 전함중 가장 무거운 전함의 무게를 구하는 프로그램을 작성하시오.

입력

첫재 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 그리드의 크기 n, 전함의 수 k, 대포를 발사한 횟수 l이 주어진다. 1 ≤ n ≤ 1,000,000,000, 1 ≤ k,l ≤ 100,000. 다음 k개 줄에는 다섯 정수 x, y, x', y', w가 주어진다. 이 숫자는 전함의 양 끝점 (x,y), (x',y') (1 ≤ x,y,x',y' ≤ n)와 무게 w를 나타낸다. (1 ≤ w ≤ 1,000,000) 다음 l개 줄에는 두 정수 a와 b가 주어진다. (1 ≤ a ≤ n, b = 0 또는 1) b가 0인 경우에는 대포를 (1,a)와 (n,a)를 연결하는 선분으로 수평 발사한 것이고, 1인 경우에는 (a,1)와 (a,n)을 연결하는 선분으로 수직 발사한 것이다.

출력

각 테스트 케이스마다 l줄을 출력한다. 매번 레이저를 발사할 때마다, 파괴한 전함 중 가장 무거운 전함의 무게를 출력한다. 만약, 파괴된 전함이 없는 경우에는 0을 출력한다.

예제 입력 1

2
5 5 2
1 2 2 5 1
1 4 2 1 2
3 5 5 4 4
3 1 3 2 3
3 3 5 3 5
4 1
4 0
5 2 2
3 1 1 3 2
4 5 1 1 3
4 1
4 0

예제 출력 1

5
2
3
0
W3sicHJvYmxlbV9pZCI6IjU0ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWQ1NjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmRcdWM3NTggXHVjNzkwXHViNzkxXHVjMmE0XHViN2VjXHVjNmI0IFx1ZDU3NFx1YWQ3MFx1Yzc3NFx1YjJlNC4gXHVjNjI0XHViMjk4XHVjNzQwIFx1YzgwNFx1ZDU2OFx1Yzc0NCBcdWQwYzBcdWFjZTAgXHVjODAxXHVhY2ZjIFx1YzJmOFx1YzZiMFx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NDQgXHVhYzAwXHVjODE1XHVkNTVjIFx1YzJlNFx1YzgwNCBcdWM1ZjBcdWMyYjVcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjODA0XHVjN2E1XHVjNzQwIG4gJnRpbWVzOyBuIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgKDEsMSlcdWM3NzRcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzA0IFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgKG4sbilcdWM3NzRcdWIyZTQuIFx1YzgwMVx1Yzc1OCBcdWQ1NjhcdWIzMDBcdWIyOTQgXHVjODA0XHVkNTY4IGtcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzgwNFx1ZDU2OCBpXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzc0ICh4PHN1Yj5pPFwvc3ViPix5PHN1Yj5pPFwvc3ViPiksICh4JiMzOTs8c3ViPmk8XC9zdWI+LHkmIzM5OzxzdWI+aTxcL3N1Yj4pXHVjNzc4IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWM4MDRcdWQ1NjhcdWM3NTggXHViYjM0XHVhYzhjXHViMjk0IHc8c3ViPmk8XC9zdWI+XHVjNzc0XHViMmU0LiBcdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHVjODA0XHVkNTY4XHVjNzQ0IFx1YmQ4MFx1YzIxOFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViODA4XHVjNzc0XHVjODAwIFx1YjMwMFx1ZDNlY1x1Yjk3YyBcdWNkMWQgbFx1YmM4OCBcdWJjMWNcdWMwYWNcdWQ1NWNcdWIyZTQuIFx1YjMwMFx1ZDNlY1x1YjI5NCBcdWMyMThcdWM5YzFcdWM3NzRcdWIwOTggXHVjMjE4XHVkM2M5IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWJjMWNcdWMwYWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHVkM2VjXHViOTdjIFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWJjMWNcdWMwYWNcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YjI5NCAoYSwxKVx1YWNmYyAoYSxuKVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMTIwXHViZDg0XHVhY2ZjIFx1YjljY1x1YjA5OFx1YjI5NCBcdWM4MDRcdWQ1NjhcdWM3NDQgXHViYWE4XHViNDUwIFx1ZDMwY1x1YWQzNFx1ZDU1Y1x1YjJlNC4gKFx1YjA1ZFx1YzgxMFx1YjNjNCBcdWQzZWNcdWQ1NjgpIFx1YjMwMFx1ZDNlY1x1Yjk3YyBcdWMyMThcdWQzYzlcdWM3M2NcdWI4NWMgXHViYzFjXHVjMGFjXHVkNTU4XHViYTc0LCBcdWI4MDhcdWM3NzRcdWM4MDBcdWIyOTQgKDEsYSlcdWM2NDAgKG4sYSlcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzEyMFx1YmQ4NFx1YWNmYyBcdWI5Y2NcdWIwOThcdWIyOTQgXHVjODA0XHVkNTY4XHViM2M0IFx1YmFhOFx1YjQ1MCBcdWQzMGNcdWFkMzRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWJjODggXHViODA4XHVjNzc0XHVjODAwIFx1Y2U5MFx1YjE3Y1x1Yzc0NCBcdWJjMWNcdWMwYWNcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWQzMGNcdWFkMzRcdWQ1NWMmbmJzcDtcdWM4MDRcdWQ1NjhcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YmIzNFx1YWM3MFx1YzZiNCBcdWM4MDRcdWQ1NjhcdWM3NDQgXHViMzAwXHVkMWI1XHViODM5XHVjNWQwXHVhYzhjIFx1YmNmNFx1YWNlMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWIyOTQgNSAmdGltZXM7IDUgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMCBcdWM4MDRcdWQ1NjhcdWM3NzQgXHViMmU0XHVjMTJmIFx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM4MDRcdWQ1NjhcdWM3NTggXHViYjM0XHVhYzhjXHViMjk0IFx1YzEyMFx1YmQ4NCBcdWM2MDZcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI5N2MgKDQsMSlcdWFjZmMgKDQsNSlcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWMyMThcdWM5YzEmbmJzcDtcdWJjMWNcdWMwYWNcdWQ1NThcdWJhNzQsIFx1YzgwNFx1ZDU2OCBcdWI0NTAgXHVhYzFjXHViOTdjIFx1ZDMwY1x1YWQzNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQzMGNcdWFkMzRcdWQ1NWMmbmJzcDtcdWM4MDRcdWQ1NjhcdWM3NTggXHViYjM0XHVhYzhjXHViMjk0IDRcdWM2NDAgNVx1Yzc3OFx1YjM3MCwgXHVhYzAwXHVjN2E1IFx1YmIzNFx1YWM3MFx1YzZiNCBcdWM4MDRcdWQ1NjhcdWM3NDAgNVx1Yzc3NFx1YmJjMFx1Yjg1YyA1XHViOTdjIFx1YmNmNFx1YWNlMFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHViODA4XHVjNzc0XHVjODAwXHViOTdjICgxLDQpXHVjNjQwICg1LDQpXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjMjE4XHVkM2M5Jm5ic3A7XHViYzFjXHVjMGFjXHVkNTU4XHViYTc0LCBcdWI0NTAgXHVjODA0XHVkNTY4XHVjNzQ0IFx1ZDMwY1x1YWQzNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQzMGNcdWFkMzRcdWQ1NWMmbmJzcDtcdWM4MDRcdWQ1NjhcdWM3NTggXHViYjM0XHVhYzhjXHViMjk0IDFcdWFjZmMgMlx1Yzc3NFx1YWNlMCwgXHViYjM0XHVhYzcwXHVjNmI0IFx1YzgwNFx1ZDU2OFx1Yzc0MCAyXHVjNzc0XHViYmMwXHViODVjIDJcdWI5N2MgXHViY2Y0XHVhY2UwXHVkNTVjXHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjk3YyBcdWJjMWNcdWMwYWNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWJiMzRcdWFjOGNcdWFjMDAgNFx1Yzc3OCBcdWM4MDRcdWQ1NjhcdWM3NDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWI4MDhcdWM3NzRcdWM4MDBcdWM1ZDAgXHVjNzU4XHVkNTc0XHVjMTFjIFx1ZDMwY1x1YWQzNFx1YjQxOFx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkMzBjXHVhZDM0XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iYXR0bGVmaWVsZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTlweDsgd2lkdGg6MjM0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzgwNFx1ZDU2OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVkNjRkXHVjOTAwXHVjNzc0XHVhYzAwIFx1YmMxY1x1YzBhY1x1ZDU1YyBcdWI4MDhcdWM3NzRcdWM4MDBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViODA4XHVjNzc0XHVjODAwXHViOTdjIFx1YmMxY1x1YzBhY1x1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQsIFx1ZDMwY1x1YWQzNFx1ZDU1YyZuYnNwO1x1YzgwNFx1ZDU2OFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViYjM0XHVhYzcwXHVjNmI0IFx1YzgwNFx1ZDU2OFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgbiwgXHVjODA0XHVkNTY4XHVjNzU4IFx1YzIxOCBrLCBcdWIzMDBcdWQzZWNcdWI5N2MgXHViYzFjXHVjMGFjXHVkNTVjIFx1ZDY5Zlx1YzIxOCBsXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMSAmbGU7IG4gJmxlOyAxLDAwMCwwMDAsMDAwLCAxICZsZTsgayxsICZsZTsgMTAwLDAwMC4gXHViMmU0XHVjNzRjIGtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlNFx1YzEyZiBcdWM4MTVcdWMyMTggeCwgeSwgeCYjMzk7LCB5JiMzOTssIHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzgwNFx1ZDU2OFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwICh4LHkpLCAoeCYjMzk7LHkmIzM5OykgKDEgJmxlOyB4LHkseCYjMzk7LHkmIzM5OyAmbGU7IG4pXHVjNjQwIFx1YmIzNFx1YWM4YyB3XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKDEgJmxlOyB3ICZsZTsgMSwwMDAsMDAwKSBcdWIyZTRcdWM3NGMgbFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBhXHVjNjQwIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGEgJmxlOyBuLCBiID0gMCBcdWI2MTBcdWIyOTQgMSkgYlx1YWMwMCAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIzMDBcdWQzZWNcdWI5N2MgKDEsYSlcdWM2NDAgKG4sYSlcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWMyMThcdWQzYzkgXHViYzFjXHVjMGFjXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YWNlMCwgMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgKGEsMSlcdWM2NDAgKGEsbilcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWMyMThcdWM5YzEgXHViYzFjXHVjMGFjXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBsXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWU0XHViYzg4IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjk3YyBcdWJjMWNcdWMwYWNcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWQzMGNcdWFkMzRcdWQ1NWMgXHVjODA0XHVkNTY4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViYjM0XHVhYzcwXHVjNmI0IFx1YzgwNFx1ZDU2OFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1ZDMwY1x1YWQzNFx1YjQxYyBcdWM4MDRcdWQ1NjhcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NDgwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmF0dGxlc2hpcCIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBhIG1lbWJlciBvZiB0aGUgcHJlc3RpZ2lvdXMgSUNQQyAoSW50ZXItQ29udGluZW50YWwgUHJvdGVjdGluZyBDb3JwcykgYW5kIGZpZ2h0aW5nIGFnYWluc3QgdGhlIGV2aWwgZW5lbXkuIFRoZSBiYXR0bGVmaWVsZCBpcyByZXByZXNlbnRlZCBieSBhbiBuICZ0aW1lczsgbiBncmlkLiBUaGUgY29vcmRpbmF0ZSBvZiB0aGUgbGVmdG1vc3QgYW5kIGxvd2VzdCBwb2ludCBpcyAoMSwxKSBhbmQgdGhhdCBvZiB0aGUgcmlnaHRtb3N0IGFuZCBoaWdoZXN0IHBvaW50IGlzIChuLG4pLiBUaGUgZW5lbXkgaGFzIGEgZmxlZXQgb2YgayBiYXR0bGVzaGlwcy4gRWFjaCBiYXR0bGVzaGlwIGkgaXMgcmVwcmVzZW50ZWQgYnkgYSBsaW5lIHNlZ21lbnQgd2hvc2UgbGVuZ3RoIGlzIGdyZWF0ZXIgdGhhbiAwIGFuZCBpdHMgZW5kcG9pbnRzIGFyZSAoeDxzdWI+aTxcL3N1Yj4seTxzdWI+aTxcL3N1Yj4pIGFuZCAoeCYjMzk7PHN1Yj5pPFwvc3ViPix5JiMzOTs8c3ViPmk8XC9zdWI+KS4gQWxzbywgaXRzIHdlaWdodCBpcyB3PHN1Yj5pPFwvc3ViPi4gWW91IGNhbiBmaXJlIGEgbGFzZXIgY2Fubm9uIGwgdGltZXMgdG8gZGVzdHJveSBiYXR0bGVzaGlwcy4gRWFjaCB0aW1lIHlvdSBjYW4gZmlyZSBpdCBlaXRoZXIgaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkuIElmIHlvdSBzaG9vdCBpdCB2ZXJ0aWNhbGx5LCB0aGUgbGFzZXIgaXMgcmVwcmVzZW50ZWQgYnkgYSBsaW5lIGxpbmtpbmcgKGEsMSkgYW5kIChhLG4pIGFuZCBhbGwgdGhlIGJhdHRsZXNoaXBzIHdoaWNoIG1lZXQgdGhlIGxpbmUgKGluY2x1ZGluZyB0aGUgZW5kcG9pbnRzKSBhcmUgZGVzdHJveWVkLiBJZiB5b3Ugc2hvb3QgaXQgaG9yaXpvbnRhbGx5LCB0aGUgbGFzZXIgaXMgcmVwcmVzZW50ZWQgYnkgYSBsaW5lIGxpbmtpbmcgKDEsYSkgYW5kIChuLGEpIGFuZCB0aG9zZSB3aGljaCBtZWV0IHRoZSBsaW5lIChpbmNsdWRpbmcgdGhlIGVuZHBvaW50cykgYXJlIGRlc3Ryb3llZC4gV2hpbGUgeW91IGFyZSBhIGJyYXZlIHNvbGRpZXIsIGR1ZSB0byB0aGUgaW5lZmZpY2llbmN5IG9mIGJ1cmVhdWNyYWN5LCB5b3UgYXJlIGFza2VkIHRvIHJlcG9ydCB0aGUgaGVhdmllc3QgYmF0dGxlc2hpcCB5b3UganVzdCBkZXN0cm95ZWQgZWFjaCB0aW1lIHlvdSBzaG9vdCB0aGUgbGFzZXIgY2Fubm9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgZXhhbXBsZSBpbiBGaWd1cmUgMS4gVGhlcmUgYXJlIGZpdmUgYmF0dGxlc2hpcHMgb24gYSA1Jm5ic3A7JnRpbWVzOyA1IGdyaWQuIFRoZSB3ZWlnaHQgb2YgYSBiYXR0bGVzaGlwIGlzIHdyaXR0ZW4gbmV4dCB0byBpdC4gQXNzdW1lIHRoYXQgd2UgZmlyc3Qgc2hvb3QgdGhlIGNhbm5vbiB2ZXJ0aWNhbGx5IGFuZCB0aGUgbGFzZXIgaXMgYSBsaW5lIGxpbmtpbmcgKDQsMSkgYW5kICg0LDUpLiBUaGVuIHR3byBiYXR0bGVzaGlwcyBhcmUgZGVzdHJveWVkOiBvbmUgd2l0aCB3ZWlnaHQgNCBhbmQgdGhlIG90aGVyIHdpdGggd2VpZ2h0IDUsIHdoaWNoIGlzIGhlYXZpZXIuIFRoZXJlZm9yZSB3ZSByZXBvcnQgNS4gTmV4dCB3ZSBzaG9vdCB0aGUgY2Fubm9uIGhvcml6b250YWxseSBhbmQgdGhlIGxhc2VyIGlzIGEgbGluZSBsaW5raW5nICgxLDQpIGFuZCAoNSw0KS4mbmJzcDtBZ2FpbiB0d28gYmF0dGxlc2hpcHMgYXJlIGRlc3Ryb3llZDogb25lIHdpdGggd2VpZ2h0IDEgYW5kIHRoZSBvdGhlciB3aXRoIHdlaWdodCAyLCB3aGljaCBpcyBoZWF2aWVyLiBXZSByZXBvcnQgMi4gTm90ZSB0aGF0IHRoZSBiYXR0bGVzaGlwIHdpdGggd2VpZ2h0IDQgaXMgYWxyZWFkeSBkZXN0cm95ZWQgYXQgdGhlIGZpcnN0IHNob290aW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JhdHRsZWZpZWxkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5OXB4OyB3aWR0aDoyMzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gQW4gZXhhbXBsZSBvZiBiYXR0bGVmaWVsZCB3aXRoIGZpdmUgYmF0dGxlc2hpcHMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBsb2NhdGlvbnMgb2YgYmF0dGxlc2hpcHMgYW5kIHlvdXIgc2hvb3RpbmcgaW5mb3JtYXRpb24sIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCByZXBvcnRzIHRoZSBoZWF2aWVzdCBiYXR0bGVzaGlwIHlvdSBkZXN0cm95ZWQgZWFjaCB0aW1lIHlvdSBzaG9vdCB0aGUgY2Fubm9uLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBpbnRlZ2VycyBuLGssIGFuZCBsLCB0aGUgc2l6ZSBvZiB0aGUgZ3JpZCwgdGhlIG51bWJlciBvZiBiYXR0bGVzaGlwcywgYW5kIHRoZSBudW1iZXIgb2YgdGltZXMgeW91IGNhbiBzaG9vdCB0aGUgbGFzZXIgY2Fubm9uLCByZXNwZWN0aXZlbHksIHdoZXJlIDEgJmxlOyBuICZsZTsgMSwwMDAsMDAwLDAwMCBhbmQgMSAmbGU7IGssbCAmbGU7IDEwMCwwMDAuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBrIGxpbmVzIGNvbnRhaW5zIGZpdmUgaW50ZWdlcnMgeCx5LHgmIzM5Oyx5JiMzOTsgYW5kIHcgc2VwYXJhdGVkIGJ5IGEgc3BhY2Ugd2hpY2ggcmVwcmVzZW50IHRoZSBlbmRwb2ludHMgb2YgYSBiYXR0bGVzaGlwICh4LHkpIGFuZCAoeCYjMzk7eSYjMzk7KSAoMSAmbGU7IHgseSx4JiMzOTsseSYjMzk7ICZsZTsgbikgYW5kIGl0cyB3ZWlnaHQgMSAmbGU7IHcgJmxlOyAxLDAwMCwwMDAuIEFsc28gZWFjaCBvZiB0aGUgZm9sbG93aW5nIGwgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIGEgYW5kIGIgd2hlcmUgMSAmbGU7IGEgJm5ic3A7bi4gRWl0aGVyIGIgPSAwIG9yIGIgPSAxLiBJZiBiID0gMCwgeW91IHNob290IHRoZSBjYW5ub24gaG9yaXpvbnRhbGx5IGFuZCB0aGUgbGFzZXIgaXMgcmVwcmVzZW50ZWQgYnkgYSBsaW5lIGxpbmtpbmcgKDEsYSkgYW5kIChuLGEpLiBJZiBiID0gMSwgeW91IHNob290IGl0IHZlcnRpY2FsbHkgYW5kIHRoZSBsYXNlciBpcyByZXByZXNlbnRlZCBieSBhIGxpbmUgbGlua2luZyAoYSwxKSBhbmQgKGEsbikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBsIGxpbmVzIGZvciBlYWNoIHRlc3QgY2FzZS4gRWFjaCBsaW5lIHNob3VsZCBjb250YWluIGFuIGludGVnZXIgdmFsdWUsIHRoZSB3ZWlnaHQgb2YgdGhlIGhlYXZpZXN0IGJhdHRsZXNoaXAgeW91IGRlc3Ryb3llZCBieSBzaG9vdGluZyB0aGUgbGFzZXIgY2Fubm9uLiBJZiB5b3UgZGVzdHJveWVkIG5vdGhpbmcsIHByaW50IDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제의 오타를 찾은 사람: apink jh05013
  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: doju
  • 데이터를 만든 사람: myungwoo