시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB4012457.143%

문제

통계상으로 상업 비행기는 꽤 안전하다. 초창기의 비행기는 기술적인 측면에서 현재의 비행기에 비해 엔진 신뢰성이 낮아서 항로상에서 인근 공항으로 부터 60분 이상 떨어져서 비행하는 것을 금지했기 때문이다. 지금도 다양한 규칙들이 존재하지만 핵심 내용은 이 "60분의 규칙"과 비슷하다. 비행기가 가장 가까운 공항에서 허용된 최대 거리 이상 멀어지면 안 된다는 것이다. 이러한 제약 사항 때문에 비행기가 곧바로 공항까지 갈 수 없는 경우도 종종 있다.

우리는 최대 허용 거리를 준수하면서 주어진 두 공항 사이를 이동하는 최단 경로를 계산해야 한다. 아래 보이는 그림은 첫 번째 테스트 케이스에 대한 자료를 나타낸다. 비행기의 항로는 반드시 주어진 세개의 원 어딘가에 존재해야 하며 2번에서 3번 공항으로 이동하려면 반드시 1번 공항의 원을 거쳐야 한다. 비행기가 공항 1에 도착할 필요는 없다.

비행기의 연료는 제한되어있기 때문에 최단 경로보다 긴 경로로 이동할 경우 연료 부족으로 도중에 착륙해야 할 수도 있다. 따라서 연료 용량에 따라 공항 1까지 가야 하는 경우가 생길 수도 있다. 공항 1까지 가는데 필요한 연료도 부족한 경우엔 도착지 까지 갈 수 없는 경우이다.

위와 같은 가정을 아래처럼 단순화 할 수 있다.

  1. 지구의 표면은 반경 6370 km 이다.
  2. 시간과 연료 소비량은 모두 이동거리에 비례한다. 즉, 우리는 이동거리에만 관심이  있다.
  3. 고도에 따른 거리 차이는 무시한다. 즉, 비행기가 표현에 따라 비행한다고 가정한다.
  4. 비행기는 필요에 따라 중간 지점의 공항에서 연료를 공급받을 수 있다. 한번 공급받을때 연료를 모두 채운다.

입력

각 테스트 케이스의 첫 번째 줄에 정수 N 과 R 이 주어진다 (2 ≤ N ≤ 25, 1 ≤ R ≤ 10 000). N은 공항의 수 이고 R은 최대 허용 거리(km)이다. 다음 N개의 줄에는 공항의 경도와 위도를 나타내는 정수 Φ, θ가 주어진다(0 ≤ Φ < 360, -90 ≤ θ ≤ 90). 공항의 번호는 각각 1부터 입력받은 순서로주어지며 두 공항이 같은 위치에 있는 경우는 없다.

이어지는 줄에는 정수 Q가 주어진다 (1 ≤ Q ≤ 100). 각각의 Q개의 줄에는 출발 공항 번호, 도착 공항 번호, 연료의 용량(최대 연료 이동할 수 있는 거리)을 나타내는 세개의 정수 s, t, c가 주어진다 (1 ≤ s,  t ≤ N, s ≠ t,  1 ≤ c ≤ 50 000). 

출력

각각의 테스트 케이스 첫 번째 줄에 예제와 같이 테스트 케이스의 번호를 출력한다. 뒤이어 한줄씩 s, t, c를 만족하는 최단 비행 경로를 소숫점 셋째 자리 까지 출력한다. 가능한 경로가 존재하지 않다면 "impossible" 을 출력한다.

예제 입력 1

3 2000
0 0
0 30
30 0
3
2 3 5000
2 3 4000
2 3 3000
2 10000
45 45
225 -45
2
1 2 50000
2 1 50000

예제 출력 1

Case 1:
4724.686
6670.648
impossible
Case 2:
impossible
impossible
W3sicHJvYmxlbV9pZCI6IjQyMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIyZTggXHViZTQ0XHVkNTg5IFx1YWNiZFx1Yjg1YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVkMWI1XHVhY2M0XHVjMGMxXHVjNzNjXHViODVjIFx1YzBjMVx1YzVjNSBcdWJlNDRcdWQ1ODlcdWFlMzBcdWIyOTQgXHVhZjY0IFx1YzU0OFx1YzgwNFx1ZDU1OFx1YjJlNC4gXHVjZDA4XHVjYzNkXHVhZTMwXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjI5NCBcdWFlMzBcdWMyMjBcdWM4MDFcdWM3NzggXHVjZTIxXHViYTc0XHVjNWQwXHVjMTFjIFx1ZDYwNFx1YzdhY1x1Yzc1OCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWM1ZDAgXHViZTQ0XHVkNTc0IFx1YzVkNFx1YzljNCBcdWMyZTBcdWI4YjBcdWMxMzFcdWM3NzQgXHViMGFlXHVjNTQ0XHVjMTFjIFx1ZDU2ZFx1Yjg1Y1x1YzBjMVx1YzVkMFx1YzExYyBcdWM3NzhcdWFkZmMgXHVhY2Y1XHVkNTZkXHVjNzNjXHViODVjIFx1YmQ4MFx1ZDEzMCA2MFx1YmQ4NCBcdWM3NzRcdWMwYzEgXHViNWE4XHVjNWI0XHVjODM4XHVjMTFjIFx1YmU0NFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTA4XHVjOWMwXHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVjOWMwXHVhZTA4XHViM2M0IFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWFkZGNcdWNlNTlcdWI0ZTRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDU3NVx1YzJlYyBcdWIwYjRcdWM2YTlcdWM3NDAgXHVjNzc0ICZxdW90OzYwXHViZDg0XHVjNzU4IFx1YWRkY1x1Y2U1OSZxdW90O1x1YWNmYyBcdWJlNDRcdWMyYjdcdWQ1NThcdWIyZTQuIFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDU2ZFx1YzVkMFx1YzExYyBcdWQ1YzhcdWM2YTlcdWI0MWMgXHVjZDVjXHViMzAwIFx1YWM3MFx1YjlhYyBcdWM3NzRcdWMwYzEgXHViYTQwXHVjNWI0XHVjOWMwXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjODFjXHVjNTdkIFx1YzBhY1x1ZDU2ZCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViZTQ0XHVkNTg5XHVhZTMwXHVhYzAwIFx1YWNlN1x1YmMxNFx1Yjg1YyZuYnNwO1x1YWNmNVx1ZDU2ZFx1YWU0Y1x1YzljMCBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjODg1XHVjODg1IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1YzhcdWM2YTkgXHVhYzcwXHViOWFjXHViOTdjIFx1YzkwMFx1YzIxOFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViNDUwIFx1YWNmNVx1ZDU2ZCBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM3OTBcdWI4Y2NcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWJlNDRcdWQ1ODlcdWFlMzBcdWM3NTggXHVkNTZkXHViODVjXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzZkMCBcdWM1YjRcdWI1MThcdWFjMDBcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCAyXHViYzg4XHVjNWQwXHVjMTFjIDNcdWJjODggXHVhY2Y1XHVkNTZkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJjMThcdWI0ZGNcdWMyZGMgMVx1YmM4OCBcdWFjZjVcdWQ1NmRcdWM3NTggXHVjNmQwXHVjNzQ0IFx1YWM3MFx1Y2NkMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWFjZjVcdWQ1NmQgMVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZnAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzQxcHg7IHdpZHRoOjM4MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmU0NFx1ZDU4OVx1YWUzMFx1Yzc1OCBcdWM1ZjBcdWI4Y2NcdWIyOTQgXHVjODFjXHVkNTVjXHViNDE4XHVjNWI0XHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViY2Y0XHViMmU0IFx1YWUzNCBcdWFjYmRcdWI4NWNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YWNiZFx1YzZiMCBcdWM1ZjBcdWI4Y2MgXHViZDgwXHVjODcxXHVjNzNjXHViODVjIFx1YjNjNFx1YzkxMVx1YzVkMCBcdWNjMjlcdWI5NTlcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM1ZjBcdWI4Y2MgXHVjNmE5XHViN2M5XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWFjZjVcdWQ1NmQgMVx1YWU0Y1x1YzljMCBcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWMwZGRcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVhY2Y1XHVkNTZkIDFcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWI4Y2NcdWIzYzQgXHViZDgwXHVjODcxXHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkNCBcdWIzYzRcdWNjMjlcdWM5YzAgXHVhZTRjXHVjOWMwIFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjMDBcdWM4MTVcdWM3NDQgXHVjNTQ0XHViNzk4XHVjYzk4XHViN2ZjIFx1YjJlOFx1YzIxY1x1ZDY1NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM5YzBcdWFkNmNcdWM3NTggXHVkNDVjXHViYTc0XHVjNzQwIFx1YmMxOFx1YWNiZCA2MzcwIGttIFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMmRjXHVhYzA0XHVhY2ZjIFx1YzVmMFx1YjhjYyBcdWMxOGNcdWJlNDRcdWI3YzlcdWM3NDAgXHViYWE4XHViNDUwIFx1Yzc3NFx1YjNkOVx1YWM3MFx1YjlhY1x1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjNmIwXHViOWFjXHViMjk0IFx1Yzc3NFx1YjNkOVx1YWM3MFx1YjlhY1x1YzVkMFx1YjljYyBcdWFkMDBcdWMyZWNcdWM3NzQmbmJzcDsgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjZTBcdWIzYzRcdWM1ZDAgXHViNTMwXHViOTc4IFx1YWM3MFx1YjlhYyBcdWNjMjhcdWM3NzRcdWIyOTQgXHViYjM0XHVjMmRjXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWQ0NWNcdWQ2MDRcdWM1ZDAgXHViNTMwXHViNzdjIFx1YmU0NFx1ZDU4OVx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmU0NFx1ZDU4OVx1YWUzMFx1YjI5NCBcdWQ1NDRcdWM2OTRcdWM1ZDAgXHViNTMwXHViNzdjIFx1YzkxMVx1YWMwNCBcdWM5YzBcdWM4MTBcdWM3NTggXHVhY2Y1XHVkNTZkXHVjNWQwXHVjMTFjIFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWFjZjVcdWFlMDlcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTVjXHViYzg4IFx1YWNmNVx1YWUwOVx1YmMxYlx1Yzc0NFx1YjU0YyBcdWM1ZjBcdWI4Y2NcdWI5N2MgXHViYWE4XHViNDUwIFx1Y2M0NFx1YzZiNFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE4gXHVhY2ZjIFIgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMiAmbGU7IE4gJmxlOyAyNSwgMSAmbGU7IFIgJmxlOyAxMCAwMDApLiBOXHVjNzQwIFx1YWNmNVx1ZDU2ZFx1Yzc1OCBcdWMyMTggXHVjNzc0XHVhY2UwIFJcdWM3NDAgXHVjZDVjXHViMzAwIFx1ZDVjOFx1YzZhOSBcdWFjNzBcdWI5YWMoa20pXHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVkNTZkXHVjNzU4IFx1YWNiZFx1YjNjNFx1YzY0MCBcdWM3MDRcdWIzYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAmUGhpOywgJnRoZXRhO1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoMCAmbGU7ICZQaGk7ICZsdDsgMzYwLCAtOTAgJmxlOyAmdGhldGE7ICZsZTsgOTApLiBcdWFjZjVcdWQ1NmRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IFx1YWMwMVx1YWMwMSAxXHViZDgwXHVkMTMwIFx1Yzc4NVx1YjgyNVx1YmMxYlx1Yzc0MCBcdWMyMWNcdWMxMWNcdWI4NWNcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHViNDUwIFx1YWNmNVx1ZDU2ZFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbGU7IFEgJmxlOyAxMDApLiBcdWFjMDFcdWFjMDFcdWM3NTggUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDljXHViYzFjIFx1YWNmNVx1ZDU2ZCBcdWJjODhcdWQ2MzgsIFx1YjNjNFx1Y2MyOSBcdWFjZjVcdWQ1NmQgXHViYzg4XHVkNjM4LCBcdWM1ZjBcdWI4Y2NcdWM3NTggXHVjNmE5XHViN2M5KFx1Y2Q1Y1x1YjMwMCBcdWM1ZjBcdWI4Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjKVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBzLCB0LCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbGU7IHMsJm5ic3A7IHQgJmxlOyBOLCBzICZuZTsgdCwmbmJzcDsgMSAmbGU7IGMgJmxlOyA1MCAwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzYwOFx1YzgxY1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI0YTRcdWM3NzRcdWM1YjQgXHVkNTVjXHVjOTA0XHVjNTI5IHMsIHQsIGNcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWJlNDRcdWQ1ODkgXHVhY2JkXHViODVjXHViOTdjIFx1YzE4Y1x1YzIyYlx1YzgxMCBcdWMxNGJcdWM5ZjggXHVjNzkwXHViOWFjIFx1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7IFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDIxMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNob3J0ZXN0IEZsaWdodCBQYXRoIiwiZGVzY3JpcHRpb24iOiI8cD5Db21tZXJjaWFsIFx1ZmIwMmlnaHRzIGFyZSBzdGF0aXN0aWNhbGx5IHF1aXRlIHNhZmUgKGluIHRlcm1zIG9mIG51bWJlciBvZiBkZWF0aHMgcGVyIHBhc3Nlbmdlci1raWxvbWV0ZXIsIG9ubHkgZ29pbmcgdG8gdGhlIG1vb24gaXMgc2FmZXIpLiBCdXQgdGhlcmUgYXJlIHN0aWxsIHJlYXNvbnMgZm9yIHByZWNhdXRpb25zIGFuZCBzYWZldHkgcmVndWxhdGlvbnMuIEFuIGVhcmx5IHN1Y2ggcnVsZSB3YXMgdGhlIHNvLWNhbGxlZCAmbGRxdW87NjAtbWludXRlIHJ1bGUsJnJkcXVvOyB3aGljaCByZXF1aXJlZCB0aGF0IGEgdHdvLWVuZ2luZSBwbGFuZSBtdXN0IGFsd2F5cyBiZSB3aXRoaW4gNjAgbWludXRlcyBvZiB0aGUgbmVhcmVzdCBhZGVxdWF0ZSBhaXJwb3J0IGFsb25nIGl0cyBlbnRpcmUgXHVmYjAyaWdodCBwYXRoLiBBIHZhcmlldHkgb2Ygc2ltaWxhciBydWxlcyBoYXZlIGV4aXN0ZWQsIGJ1dCBhdCB0aGVpciBjb3JlLCB0aGV5IHJlbWFpbiB0aGUgc2FtZTogdGhlIFx1ZmIwMmlnaHQgcGF0aCBjYW4gbm90IHRha2UgdGhlIGFpcnBsYW5lIG1vcmUgdGhhbiBhIGNlcnRhaW4gbWF4aW11bSBhbGxvd2VkIGRpc3RhbmNlIGZyb20gdGhlIG5lYXJlc3QgYWlycG9ydC4gV2l0aCB0aGVzZSByZXN0cmljdGlvbnMsIHBsYW5lcyBjYW5ub3QgYWx3YXlzIHVzZSBhIGRpcmVjdCByb3V0ZSBmb3IgXHVmYjAyeWluZyBmcm9tIG9uZSBhaXJwb3J0IHRvIGFub3RoZXIuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSB3ZSB3aWxsIGNvbXB1dGUgdGhlIHNob3J0ZXN0IFx1ZmIwMmlnaHQgcGF0aCBiZXR3ZWVuIHR3byBhaXJwb3J0cyB3aGlsZSBhZGhlcmluZyB0byBhIG1heGltdW0gYWxsb3dlZCBkaXN0YW5jZSBydWxlLiBJbiB0aGUgXHVmYjAxZ3VyZSBiZWxvdywgd2hpY2ggaWxsdXN0cmF0ZXMgdGhlIFx1ZmIwMXJzdCBzYW1wbGUgdGVzdCBjYXNlLCBhbnkgXHVmYjAyaWdodCByb3V0ZSBoYXMgdG8gc3RheSB3aXRoaW4gdGhlIHRocmVlIGNpcmNsZXMuIFRodXMgYSBwbGFuZSBnb2luZyBmcm9tIGFpcnBvcnQgMiB0byBhaXJwb3J0IDMgaGFzIHRvIGRldG91ciBmcm9tIHRoZSBkaXJlY3Qgcm91dGUgdmlhIHRoZSByZWdpb24gYXJvdW5kIGFpcnBvcnQgMS4gTm90ZSB0aGF0IHRoZSBwbGFuZSB3b3VsZCBub3QgbmVjZXNzYXJpbHkgaGF2ZSB0byBnbyB0byBhaXJwb3J0IDEgaXRzZWxmLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NmcC5wbmdcIiBzdHlsZT1cImhlaWdodDozNDFweDsgd2lkdGg6MzgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhpbmdzIGFyZSBmdXJ0aGVyIGNvbXBsaWNhdGVkIGJ5IHRoZSBmYWN0IHRoYXQgcGxhbmVzIGhhdmUgbGltaXRlZCBmdWVsIHN1cHBseSwgYW5kIHRvIGdvIGxvbmdlciBkaXN0YW5jZXMgdGhleSBtYXkgbmVlZCB0byBtYWtlIGEgc3RvcG92ZXIgYXQgaW50ZXJtZWRpYXRlIGFpcnBvcnRzLiBUaHVzLCBkZXBlbmRpbmcgb24gdGhlIGZ1ZWwgY2FwYWNpdHksIGEgcGxhbmUgZ29pbmcgZnJvbSBhaXJwb3J0IDIgdG8gYWlycG9ydCAzIGluIHRoZSBcdWZiMDFndXJlIG1pZ2h0IGhhdmUgdG8gc3RvcCBvdmVyIGF0IGFpcnBvcnQgMSAob3IgdGhlIGZ1ZWwgY2FwYWNpdHkgbWlnaHQgYmUgdG9vIGxvdyBldmVuIHRvIGdvIHRvIGFpcnBvcnQgMSwgaW4gd2hpY2ggY2FzZSB0aGUgdHJpcCB3b3VsZCBiZSBpbXBvc3NpYmxlIHRvIG1ha2UpLjxcL3A+XHJcblxyXG48cD5XZSBtYWtlIHRoZSBmb2xsb3dpbmcgc2ltcGxpZnlpbmcgYXNzdW1wdGlvbnM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+VGhlIHN1cmZhY2UmbmJzcDtvZiB0aGUgZWFydGggaXMgYSBzcGhlcmUgb2YgcmFkaXVzIDYzNzAga20uPFwvbGk+XHJcblx0PGxpPkJvdGggdGltZSBhbmQgZnVlbCBjb25zdW1wdGlvbiBhcmUgZGlyZWN0bHkgcHJvcG9ydGlvbmFsIHRvIGRpc3RhbmNlIHRyYXZlbGVkLiBJbiBvdGhlciB3b3JkcyB3ZSBhcmUgaW50ZXJlc3RlZCBvbmx5IGluIHRvdGFsIGRpc3RhbmNlIHRyYXZlbGVkLjxcL2xpPlxyXG5cdDxsaT5UaGUgZGlmZmVyZW5jZSBpbiBkaXN0YW5jZSBjYXVzZWQgYnkgcGxhbmVzIFx1ZmIwMnlpbmcgYXQgZGlmZmVyZW50IGFsdGl0dWRlcyBpcyBuZWdsaWdpYmxlLiBUaHVzLCBlZmZlY3RpdmVseSwgd2UgYXNzdW1lIHRoZW0gdG8gYmUgXHVmYjAyeWluZyBhbG9uZyB0aGUgZWFydGgmcnNxdW87cyBzdXJmYWNlLjxcL2xpPlxyXG5cdDxsaT5BIHBsYW5lIG1heSZuYnNwO3N0b3AgZm9yIHJlZnVlbGluZyBhdCBhcyBtYW55IGludGVybWVkaWF0ZSBhaXJwb3J0cyBhcyBuZWVkZWQsIGVhY2ggdGltZSBnZXR0aW5nIGEgZnVsbCB0YW5rLjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIFIsIHdoZXJlIDIgJmxlOyBOICZsZTsgMjUgaXMgdGhlIG51bWJlciBvZiBhaXJwb3J0cyBhbmQgMSAmbGU7IFIgJmxlOyAxMCAwMDAgaXMgdGhlIG1heGltdW0gYWxsb3dlZCBcdWZiMDJpZ2h0IGRpc3RhbmNlIChpbiBrbSkgZnJvbSB0aGUgbmVhcmVzdCBhaXJwb3J0LiBFYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzICZQaGk7LCAmdGhldGE7IHNhdGlzZnlpbmcgMCAmbGU7ICZQaGk7ICZsdDsgMzYwIGFuZCAtOTAgJmxlOyAmdGhldGE7ICZsZTsgOTAsIHRoZSBsb25naXR1ZGUgYW5kIGxhdGl0dWRlIChyZXNwZWN0aXZlbHkpIG9mIGFuIGFpcnBvcnQsIGluIGRlZ3JlZXMuIFRoZSBhaXJwb3J0cyBhcmUgbnVtYmVyZWQgYWNjb3JkaW5nIHRvIHRoZWlyIG9yZGVyIGluIHRoZSBpbnB1dCBzdGFydGluZyBmcm9tIG9uZS4gTm8gdHdvIGFpcnBvcnRzIGFyZSBhdCB0aGUgc2FtZSBwb3NpdGlvbi48XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIHRoaXMgaXMgYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBRLCBzYXRpc2Z5aW5nIDEgJmxlOyBRICZsZTsgMTAwLiBFYWNoIG9mIHRoZSBuZXh0IFEgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgcywgdCwgYyBzYXRpc2Z5aW5nIDEgJmxlOyBzOyB0ICZsZTsgTiwgcyAmbmU7IHQsIGFuZCAxICZsZTsgYyAmbGU7IDUwIDAwMCwgaW5kaWNhdGluZyBhIHBsYW5lIGdvaW5nIGZyb20gYWlycG9ydCBzIHRvIGFpcnBvcnQgdCB3aXRoIGEgZnVlbCBjYXBhY2l0eSB5aWVsZGluZyBhIHJhbmdlIG9mIGMga20uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBkaXNwbGF5IHRoZSBjYXNlIG51bWJlciBmb2xsb3dlZCBieSBvbmUgbGluZSBmb3IgZWFjaCBxdWVyeSBjb250YWluaW5nIHRoZSBsZW5ndGggaW4ga20gb2YgdGhlIHNob3J0ZXN0IFx1ZmIwMmlnaHQgcGF0aCBiZXR3ZWVuIGFpcnBvcnQgcyBhbmQgdCwgc3ViamVjdCB0byB0aGUgZnVlbCBjb25zdHJhaW50IGMuIERpc3BsYXkgdGhlIGxlbmd0aCBhY2N1cmF0ZSB0byB0aHJlZSBkZWNpbWFsIHBsYWNlcy4gSWYgdGhlcmUgaXMgbm8gcGVybWlzc2libGUgcGF0aCBiZXR3ZWVuIHRoZSB0d28gYWlycG9ydHMsIHRoZW4gZGlzcGxheSB0aGUgd29yZCBpbXBvc3NpYmxlIGluc3RlYWQuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoZSBhbnN3ZXIgaXMgbnVtZXJpY2FsbHkgc3RhYmxlIGZvciBwZXJ0dXJiYXRpb25zIG9mIHVwIHRvIDA6MSBrbSBvZiBSIG9yIGMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > World Finals > ACM-ICPC World Finals 2012 J번

  • 문제를 번역한 사람: lll4592