시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 256 MB 1390 198 110 22.088%

문제

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

전장은 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+XHViMzAwXHVkM2VjXHViOTdjIFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWJjMWNcdWMwYWNcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YjI5NCAoYSwxKVx1YWNmYyAoYSxuKVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMTIwXHViZDg0XHVhY2ZjIFx1YjljY1x1YjA5OFx1YjI5NCBcdWM4MDRcdWQ1NjhcdWM3NDQgXHViYWE4XHViNDUwIFx1ZDMwY1x1YWQzNFx1ZDU1Y1x1YjJlNC4gKFx1YjA1ZFx1YzgxMFx1YjNjNCBcdWQzZWNcdWQ1NjgpIFx1YjMwMFx1ZDNlY1x1Yjk3YyBcdWMyMThcdWQzYzlcdWM3M2NcdWI4NWMgXHViYzFjXHVjMGFjXHVkNTU4XHViYTc0LCBcdWI4MDhcdWM3NzRcdWM4MDBcdWIyOTQgKDEsYSlcdWM2NDAgKG4sYSlcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzEyMFx1YmQ4NFx1YWNmYyBcdWI5Y2NcdWIwOThcdWIyOTQgXHVjODA0XHVkNTY4XHViM2M0IFx1YmFhOFx1YjQ1MCBcdWQzMGNcdWFkMzRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWJjODggXHViODA4XHVjNzc0XHVjODAwIFx1Y2U5MFx1YjE3Y1x1Yzc0NCBcdWJjMWNcdWMwYWNcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWQzMGNcdWFkMzRcdWQ1NWMmbmJzcDtcdWM4MDRcdWQ1NjhcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YmIzNFx1YWM3MFx1YzZiNCBcdWM4MDRcdWQ1NjhcdWM3NDQgXHViMzAwXHVkMWI1XHViODM5XHVjNWQwXHVhYzhjIFx1YmNmNFx1YWNlMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWIyOTQgNSAmdGltZXM7IDUgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMCBcdWM4MDRcdWQ1NjhcdWM3NzQgXHViMmU0XHVjMTJmIFx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM4MDRcdWQ1NjhcdWM3NTggXHViYjM0XHVhYzhjXHViMjk0IFx1YzEyMFx1YmQ4NCBcdWM2MDZcdWM1ZDAgXHVjMzY4XHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjk3YyAoNCwxKVx1YWNmYyAoNCw1KVx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YzIxOFx1YzljMSZuYnNwO1x1YmMxY1x1YzBhY1x1ZDU1OFx1YmE3NCwgXHVjODA0XHVkNTY4IFx1YjQ1MCBcdWFjMWNcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDMwY1x1YWQzNFx1ZDU1YyZuYnNwO1x1YzgwNFx1ZDU2OFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWIyOTQgNFx1YzY0MCA1XHVjNzc4XHViMzcwLCBcdWFjMDBcdWM3YTUgXHViYjM0XHVhYzcwXHVjNmI0IFx1YzgwNFx1ZDU2OFx1Yzc0MCA1XHVjNzc0XHViYmMwXHViODVjIDVcdWI5N2MgXHViY2Y0XHVhY2UwXHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI5N2MgKDEsNClcdWM2NDAgKDUsNClcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWMyMThcdWQzYzkmbmJzcDtcdWJjMWNcdWMwYWNcdWQ1NThcdWJhNzQsIFx1YjQ1MCBcdWM4MDRcdWQ1NjhcdWM3NDQgXHVkMzBjXHVhZDM0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDMwY1x1YWQzNFx1ZDU1YyZuYnNwO1x1YzgwNFx1ZDU2OFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWIyOTQgMVx1YWNmYyAyXHVjNzc0XHVhY2UwLCBcdWJiMzRcdWFjNzBcdWM2YjQgXHVjODA0XHVkNTY4XHVjNzQwIDJcdWM3NzRcdWJiYzBcdWI4NWMgMlx1Yjk3YyBcdWJjZjRcdWFjZTBcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViODA4XHVjNzc0XHVjODAwXHViOTdjIFx1YmMxY1x1YzBhY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YmIzNFx1YWM4Y1x1YWMwMCA0XHVjNzc4IFx1YzgwNFx1ZDU2OFx1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjgwOFx1Yzc3NFx1YzgwMFx1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHVkMzBjXHVhZDM0XHViNDE4XHVjNWM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQzMGNcdWFkMzRcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JhdHRsZWZpZWxkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5OXB4OyB3aWR0aDoyMzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjODA0XHVkNTY4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWQ2NGRcdWM5MDBcdWM3NzRcdWFjMDAgXHViYzFjXHVjMGFjXHVkNTVjIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI4MDhcdWM3NzRcdWM4MDBcdWI5N2MgXHViYzFjXHVjMGFjXHVkNTYwIFx1YjU0Y1x1YjljOFx1YjJlNCwgXHVkMzBjXHVhZDM0XHVkNTVjJm5ic3A7XHVjODA0XHVkNTY4XHVjOTExIFx1YWMwMFx1YzdhNSBcdWJiMzRcdWFjNzBcdWM2YjQgXHVjODA0XHVkNTY4XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzdhYyBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBuLCBcdWM4MDRcdWQ1NjhcdWM3NTggXHVjMjE4IGssIFx1YjMwMFx1ZDNlY1x1Yjk3YyBcdWJjMWNcdWMwYWNcdWQ1NWMgXHVkNjlmXHVjMjE4IGxcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCwwMDAsIDEgJmxlOyBrLGwgJmxlOyAxMDAsMDAwLiBcdWIyZTRcdWM3NGMga1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjMTJmIFx1YzgxNVx1YzIxOCB4LCB5LCB4JiMzOTssIHkmIzM5Oywgd1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjODA0XHVkNTY4XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTAgKHgseSksICh4JiMzOTsseSYjMzk7KSAoMSAmbGU7IHgseSx4JiMzOTsseSYjMzk7ICZsZTsgbilcdWM2NDAgXHViYjM0XHVhYzhjIHdcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAoMSAmbGU7IHcgJmxlOyAxLDAwMCwwMDApIFx1YjJlNFx1Yzc0YyBsXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IGFcdWM2NDAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYSAmbGU7IG4sIGIgPSAwIFx1YjYxMFx1YjI5NCAxKSBiXHVhYzAwIDBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjMwMFx1ZDNlY1x1Yjk3YyAoMSxhKVx1YzY0MCAobixhKVx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YzIxOFx1ZDNjOSBcdWJjMWNcdWMwYWNcdWQ1NWMgXHVhYzgzXHVjNzc0XHVhY2UwLCAxXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAoYSwxKVx1YzY0MCAoYSxuKVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YzIxOFx1YzljMSBcdWJjMWNcdWMwYWNcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IGxcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5ZTRcdWJjODggXHViODA4XHVjNzc0XHVjODAwXHViOTdjIFx1YmMxY1x1YzBhY1x1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQsIFx1ZDMwY1x1YWQzNFx1ZDU1YyBcdWM4MDRcdWQ1NjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJiMzRcdWFjNzBcdWM2YjQgXHVjODA0XHVkNTY4XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVkMzBjXHVhZDM0XHViNDFjIFx1YzgwNFx1ZDU2OFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0ODAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYXR0bGVzaGlwIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGEgbWVtYmVyIG9mIHRoZSBwcmVzdGlnaW91cyBJQ1BDIChJbnRlci1Db250aW5lbnRhbCBQcm90ZWN0aW5nIENvcnBzKSBhbmQgZmlnaHRpbmcgYWdhaW5zdCB0aGUgZXZpbCBlbmVteS4gVGhlIGJhdHRsZWZpZWxkIGlzIHJlcHJlc2VudGVkIGJ5IGFuIG4gJnRpbWVzOyBuIGdyaWQuIFRoZSBjb29yZGluYXRlIG9mIHRoZSBsZWZ0bW9zdCBhbmQgbG93ZXN0IHBvaW50IGlzICgxLDEpIGFuZCB0aGF0IG9mIHRoZSByaWdodG1vc3QgYW5kIGhpZ2hlc3QgcG9pbnQgaXMgKG4sbikuIFRoZSBlbmVteSBoYXMgYSBmbGVldCBvZiBrIGJhdHRsZXNoaXBzLiBFYWNoIGJhdHRsZXNoaXAgaSBpcyByZXByZXNlbnRlZCBieSBhIGxpbmUgc2VnbWVudCB3aG9zZSBsZW5ndGggaXMgZ3JlYXRlciB0aGFuIDAgYW5kIGl0cyBlbmRwb2ludHMgYXJlICh4PHN1Yj5pPFwvc3ViPix5PHN1Yj5pPFwvc3ViPikgYW5kICh4JiMzOTs8c3ViPmk8XC9zdWI+LHkmIzM5OzxzdWI+aTxcL3N1Yj4pLiBBbHNvLCBpdHMgd2VpZ2h0IGlzIHc8c3ViPmk8XC9zdWI+LiBZb3UgY2FuIGZpcmUgYSBsYXNlciBjYW5ub24gbCB0aW1lcyB0byBkZXN0cm95IGJhdHRsZXNoaXBzLiBFYWNoIHRpbWUgeW91IGNhbiBmaXJlIGl0IGVpdGhlciBob3Jpem9udGFsbHkgb3IgdmVydGljYWxseS4gSWYgeW91IHNob290IGl0IHZlcnRpY2FsbHksIHRoZSBsYXNlciBpcyByZXByZXNlbnRlZCBieSBhIGxpbmUgbGlua2luZyAoYSwxKSBhbmQgKGEsbikgYW5kIGFsbCB0aGUgYmF0dGxlc2hpcHMgd2hpY2ggbWVldCB0aGUgbGluZSAoaW5jbHVkaW5nIHRoZSBlbmRwb2ludHMpIGFyZSBkZXN0cm95ZWQuIElmIHlvdSBzaG9vdCBpdCBob3Jpem9udGFsbHksIHRoZSBsYXNlciBpcyByZXByZXNlbnRlZCBieSBhIGxpbmUgbGlua2luZyAoMSxhKSBhbmQgKG4sYSkgYW5kIHRob3NlIHdoaWNoIG1lZXQgdGhlIGxpbmUgKGluY2x1ZGluZyB0aGUgZW5kcG9pbnRzKSBhcmUgZGVzdHJveWVkLiBXaGlsZSB5b3UgYXJlIGEgYnJhdmUgc29sZGllciwgZHVlIHRvIHRoZSBpbmVmZmljaWVuY3kgb2YgYnVyZWF1Y3JhY3ksIHlvdSBhcmUgYXNrZWQgdG8gcmVwb3J0IHRoZSBoZWF2aWVzdCBiYXR0bGVzaGlwIHlvdSBqdXN0IGRlc3Ryb3llZCBlYWNoIHRpbWUgeW91IHNob290IHRoZSBsYXNlciBjYW5ub24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSBleGFtcGxlIGluIEZpZ3VyZSAxLiBUaGVyZSBhcmUgZml2ZSBiYXR0bGVzaGlwcyBvbiBhIDUmbmJzcDsmdGltZXM7IDUgZ3JpZC4gVGhlIHdlaWdodCBvZiBhIGJhdHRsZXNoaXAgaXMgd3JpdHRlbiBuZXh0IHRvIGl0LiBBc3N1bWUgdGhhdCB3ZSBmaXJzdCBzaG9vdCB0aGUgY2Fubm9uIHZlcnRpY2FsbHkgYW5kIHRoZSBsYXNlciBpcyBhIGxpbmUgbGlua2luZyAoNCwxKSBhbmQgKDQsNSkuIFRoZW4gdHdvIGJhdHRsZXNoaXBzIGFyZSBkZXN0cm95ZWQ6IG9uZSB3aXRoIHdlaWdodCA0IGFuZCB0aGUgb3RoZXIgd2l0aCB3ZWlnaHQgNSwgd2hpY2ggaXMgaGVhdmllci4gVGhlcmVmb3JlIHdlIHJlcG9ydCA1LiBOZXh0IHdlIHNob290IHRoZSBjYW5ub24gaG9yaXpvbnRhbGx5IGFuZCB0aGUgbGFzZXIgaXMgYSBsaW5lIGxpbmtpbmcgKDEsNCkgYW5kICg1LDQpLiZuYnNwO0FnYWluIHR3byBiYXR0bGVzaGlwcyBhcmUgZGVzdHJveWVkOiBvbmUgd2l0aCB3ZWlnaHQgMSBhbmQgdGhlIG90aGVyIHdpdGggd2VpZ2h0IDIsIHdoaWNoIGlzIGhlYXZpZXIuIFdlIHJlcG9ydCAyLiBOb3RlIHRoYXQgdGhlIGJhdHRsZXNoaXAgd2l0aCB3ZWlnaHQgNCBpcyBhbHJlYWR5IGRlc3Ryb3llZCBhdCB0aGUgZmlyc3Qgc2hvb3RpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmF0dGxlZmllbGQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk5cHg7IHdpZHRoOjIzNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBBbiBleGFtcGxlIG9mIGJhdHRsZWZpZWxkIHdpdGggZml2ZSBiYXR0bGVzaGlwcy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGxvY2F0aW9ucyBvZiBiYXR0bGVzaGlwcyBhbmQgeW91ciBzaG9vdGluZyBpbmZvcm1hdGlvbiwgd3JpdGUgYSBwcm9ncmFtIHdoaWNoIHJlcG9ydHMgdGhlIGhlYXZpZXN0IGJhdHRsZXNoaXAgeW91IGRlc3Ryb3llZCBlYWNoIHRpbWUgeW91IHNob290IHRoZSBjYW5ub24uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGludGVnZXJzIG4saywgYW5kIGwsIHRoZSBzaXplIG9mIHRoZSBncmlkLCB0aGUgbnVtYmVyIG9mIGJhdHRsZXNoaXBzLCBhbmQgdGhlIG51bWJlciBvZiB0aW1lcyB5b3UgY2FuIHNob290IHRoZSBsYXNlciBjYW5ub24sIHJlc3BlY3RpdmVseSwgd2hlcmUgMSAmbGU7IG4gJmxlOyAxLDAwMCwwMDAsMDAwIGFuZCAxICZsZTsgayxsICZsZTsgMTAwLDAwMC4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIGsgbGluZXMgY29udGFpbnMgZml2ZSBpbnRlZ2VycyB4LHkseCYjMzk7LHkmIzM5OyBhbmQgdyBzZXBhcmF0ZWQgYnkgYSBzcGFjZSB3aGljaCByZXByZXNlbnQgdGhlIGVuZHBvaW50cyBvZiBhIGJhdHRsZXNoaXAgKHgseSkgYW5kICh4JiMzOTt5JiMzOTspICgxICZsZTsgeCx5LHgmIzM5Oyx5JiMzOTsgJmxlOyBuKSBhbmQgaXRzIHdlaWdodCAxICZsZTsgdyAmbGU7IDEsMDAwLDAwMC4gQWxzbyBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgbCBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgYSBhbmQgYiB3aGVyZSAxICZsZTsgYSAmbmJzcDtuLiBFaXRoZXIgYiA9IDAgb3IgYiA9IDEuIElmIGIgPSAwLCB5b3Ugc2hvb3QgdGhlIGNhbm5vbiBob3Jpem9udGFsbHkgYW5kIHRoZSBsYXNlciBpcyByZXByZXNlbnRlZCBieSBhIGxpbmUgbGlua2luZyAoMSxhKSBhbmQgKG4sYSkuIElmIGIgPSAxLCB5b3Ugc2hvb3QgaXQgdmVydGljYWxseSBhbmQgdGhlIGxhc2VyIGlzIHJlcHJlc2VudGVkIGJ5IGEgbGluZSBsaW5raW5nIChhLDEpIGFuZCAoYSxuKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IGwgbGluZXMgZm9yIGVhY2ggdGVzdCBjYXNlLiBFYWNoIGxpbmUgc2hvdWxkIGNvbnRhaW4gYW4gaW50ZWdlciB2YWx1ZSwgdGhlIHdlaWdodCBvZiB0aGUgaGVhdmllc3QgYmF0dGxlc2hpcCB5b3UgZGVzdHJveWVkIGJ5IHNob290aW5nIHRoZSBsYXNlciBjYW5ub24uIElmIHlvdSBkZXN0cm95ZWQgbm90aGluZywgcHJpbnQgMC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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