시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 2 1 1 50.000%

문제

통계상으로 상업 비행기는 꽤 안전하다. 초창기의 비행기는 기술적인 측면에서 현재의 비행기에 비해 엔진 신뢰성이 낮아서 항로상에서 인근 공항으로 부터 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+XHVkMWI1XHVhY2M0XHVjMGMxXHVjNzNjXHViODVjIFx1YzBjMVx1YzVjNSBcdWJlNDRcdWQ1ODlcdWFlMzBcdWIyOTQgXHVhZjY0IFx1YzU0OFx1YzgwNFx1ZDU1OFx1YjJlNC4gXHVjZDA4XHVjYzNkXHVhZTMwXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjI5NCBcdWFlMzBcdWMyMjBcdWM4MDFcdWM3NzggXHVjZTIxXHViYTc0XHVjNWQwXHVjMTFjIFx1ZDYwNFx1YzdhY1x1Yzc1OCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWM1ZDAgXHViZTQ0XHVkNTc0IFx1YzVkNFx1YzljNCBcdWMyZTBcdWI4YjBcdWMxMzFcdWM3NzQgXHViMGFlXHVjNTQ0XHVjMTFjIFx1ZDU2ZFx1Yjg1Y1x1YzBjMVx1YzVkMFx1YzExYyBcdWM3NzhcdWFkZmMgXHVhY2Y1XHVkNTZkXHVjNzNjXHViODVjIFx1YmQ4MFx1ZDEzMCA2MFx1YmQ4NCBcdWM3NzRcdWMwYzEgXHViNWE4XHVjNWI0XHVjODM4XHVjMTFjIFx1YmU0NFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTA4XHVjOWMwXHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVjOWMwXHVhZTA4XHViM2M0IFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWFkZGNcdWNlNTlcdWI0ZTRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDU3NVx1YzJlYyBcdWIwYjRcdWM2YTlcdWM3NDAgXHVjNzc0ICZxdW90OzYwXHViZDg0XHVjNzU4IFx1YWRkY1x1Y2U1OSZxdW90O1x1YWNmYyBcdWJlNDRcdWMyYjdcdWQ1NThcdWIyZTQuIFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDU2ZFx1YzVkMFx1YzExYyBcdWQ1YzhcdWM2YTlcdWI0MWMgXHVjZDVjXHViMzAwIFx1YWM3MFx1YjlhYyBcdWM3NzRcdWMwYzEgXHViYTQwXHVjNWI0XHVjOWMwXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM4MWNcdWM1N2QgXHVjMGFjXHVkNTZkIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWFjMDAgXHVhY2U3XHViYzE0XHViODVjJm5ic3A7XHVhY2Y1XHVkNTZkXHVhZTRjXHVjOWMwIFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM4ODVcdWM4ODUgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDVjOFx1YzZhOSBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjOTAwXHVjMjE4XHVkNTU4XHViYTc0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWI0NTAgXHVhY2Y1XHVkNTZkIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM1NDRcdWI3OTggXHViY2Y0XHVjNzc0XHViMjk0IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1Yzc5MFx1YjhjY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yzc1OCBcdWQ1NmRcdWI4NWNcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMxMzhcdWFjMWNcdWM3NTggXHVjNmQwIFx1YzViNFx1YjUxOFx1YWMwMFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwIDJcdWJjODhcdWM1ZDBcdWMxMWMgM1x1YmM4OCBcdWFjZjVcdWQ1NmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHViYTc0IFx1YmMxOFx1YjRkY1x1YzJkYyAxXHViYzg4IFx1YWNmNVx1ZDU2ZFx1Yzc1OCBcdWM2ZDBcdWM3NDQgXHVhYzcwXHVjY2QwXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViZTQ0XHVkNTg5XHVhZTMwXHVhYzAwIFx1YWNmNVx1ZDU2ZCAxXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NmcC5wbmdcIiBzdHlsZT1cImhlaWdodDozNDFweDsgd2lkdGg6MzgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViZTQ0XHVkNTg5XHVhZTMwXHVjNzU4IFx1YzVmMFx1YjhjY1x1YjI5NCBcdWM4MWNcdWQ1NWNcdWI0MThcdWM1YjRcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWJjZjRcdWIyZTQgXHVhZTM0IFx1YWNiZFx1Yjg1Y1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YzVmMFx1YjhjYyBcdWJkODBcdWM4NzFcdWM3M2NcdWI4NWMgXHViM2M0XHVjOTExXHVjNWQwIFx1Y2MyOVx1Yjk1OVx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzVmMFx1YjhjYyBcdWM2YTlcdWI3YzlcdWM1ZDAgXHViNTMwXHViNzdjIFx1YWNmNVx1ZDU2ZCAxXHVhZTRjXHVjOWMwIFx1YWMwMFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzBkZFx1YWUzOCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWFjZjVcdWQ1NmQgMVx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YjhjY1x1YjNjNCBcdWJkODBcdWM4NzFcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNWQ0IFx1YjNjNFx1Y2MyOVx1YzljMCBcdWFlNGNcdWM5YzAgXHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWMwMFx1YzgxNVx1Yzc0NCBcdWM1NDRcdWI3OThcdWNjOThcdWI3ZmMgXHViMmU4XHVjMjFjXHVkNjU0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YzljMFx1YWQ2Y1x1Yzc1OCBcdWQ0NWNcdWJhNzRcdWM3NDAgXHViYzE4XHVhY2JkIDYzNzAga20gXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyZGNcdWFjMDRcdWFjZmMgXHVjNWYwXHViOGNjIFx1YzE4Y1x1YmU0NFx1YjdjOVx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjNzc0XHViM2Q5XHVhYzcwXHViOWFjXHVjNWQwIFx1YmU0NFx1Yjg0MFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0XHViM2Q5XHVhYzcwXHViOWFjXHVjNWQwXHViOWNjIFx1YWQwMFx1YzJlY1x1Yzc3NCZuYnNwOyBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWNlMFx1YjNjNFx1YzVkMCBcdWI1MzBcdWI5NzggXHVhYzcwXHViOWFjIFx1Y2MyOFx1Yzc3NFx1YjI5NCBcdWJiMzRcdWMyZGNcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHViZTQ0XHVkNTg5XHVhZTMwXHVhYzAwIFx1ZDQ1Y1x1ZDYwNFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViZTQ0XHVkNTg5XHVkNTVjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZTQ0XHVkNTg5XHVhZTMwXHViMjk0IFx1ZDU0NFx1YzY5NFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMFx1Yzc1OCBcdWFjZjVcdWQ1NmRcdWM1ZDBcdWMxMWMgXHVjNWYwXHViOGNjXHViOTdjIFx1YWNmNVx1YWUwOVx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NWNcdWJjODggXHVhY2Y1XHVhZTA5XHViYzFiXHVjNzQ0XHViNTRjIFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVjYzQ0XHVjNmI0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTiBcdWFjZmMgUiBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgyICZsZTsgTiAmbGU7IDI1LCAxICZsZTsgUiAmbGU7IDEwIDAwMCkuIE5cdWM3NDAgXHVhY2Y1XHVkNTZkXHVjNzU4IFx1YzIxOCBcdWM3NzRcdWFjZTAgUlx1Yzc0MCBcdWNkNWNcdWIzMDAgXHVkNWM4XHVjNmE5IFx1YWM3MFx1YjlhYyhrbSlcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWQ1NmRcdWM3NTggXHVhY2JkXHViM2M0XHVjNjQwIFx1YzcwNFx1YjNjNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4ICZQaGk7LCAmdGhldGE7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgwICZsZTsgJlBoaTsgJmx0OyAzNjAsIC05MCAmbGU7ICZ0aGV0YTsgJmxlOyA5MCkuIFx1YWNmNVx1ZDU2ZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgXHVhYzAxXHVhYzAxIDFcdWJkODBcdWQxMzAgXHVjNzg1XHViODI1XHViYzFiXHVjNzQwIFx1YzIxY1x1YzExY1x1Yjg1Y1x1YzhmY1x1YzViNFx1YzljMFx1YmE3MCBcdWI0NTAgXHVhY2Y1XHVkNTZkXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgUSAmbGU7IDEwMCkuIFx1YWMwMVx1YWMwMVx1Yzc1OCBRXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNkOWNcdWJjMWMgXHVhY2Y1XHVkNTZkIFx1YmM4OFx1ZDYzOCwgXHViM2M0XHVjYzI5IFx1YWNmNVx1ZDU2ZCBcdWJjODhcdWQ2MzgsIFx1YzVmMFx1YjhjY1x1Yzc1OCBcdWM2YTlcdWI3YzkoXHVjZDVjXHViMzAwIFx1YzVmMFx1YjhjYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWMpXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzhcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHMsIHQsIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgcywmbmJzcDsgdCAmbGU7IE4sIHMgJm5lOyB0LCZuYnNwOyAxICZsZTsgYyAmbGU7IDUwIDAwMCkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNjA4XHVjODFjXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjRhNFx1Yzc3NFx1YzViNCBcdWQ1NWNcdWM5MDRcdWM1MjkgcywgdCwgY1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjZDVjXHViMmU4IFx1YmU0NFx1ZDU4OSBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjMThjXHVjMjJiXHVjODEwIFx1YzE0Ylx1YzlmOCBcdWM3OTBcdWI5YWMgXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0ICZxdW90O2ltcG9zc2libGUmcXVvdDsgXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2hvcnRlc3QgRmxpZ2h0IFBhdGgiLCJkZXNjcmlwdGlvbiI6IjxwPkNvbW1lcmNpYWwgXHVmYjAyaWdodHMgYXJlIHN0YXRpc3RpY2FsbHkgcXVpdGUgc2FmZSAoaW4gdGVybXMgb2YgbnVtYmVyIG9mIGRlYXRocyBwZXIgcGFzc2VuZ2VyLWtpbG9tZXRlciwgb25seSBnb2luZyB0byB0aGUgbW9vbiBpcyBzYWZlcikuIEJ1dCB0aGVyZSBhcmUgc3RpbGwgcmVhc29ucyBmb3IgcHJlY2F1dGlvbnMgYW5kIHNhZmV0eSByZWd1bGF0aW9ucy4gQW4gZWFybHkgc3VjaCBydWxlIHdhcyB0aGUgc28tY2FsbGVkICZsZHF1bzs2MC1taW51dGUgcnVsZSwmcmRxdW87IHdoaWNoIHJlcXVpcmVkIHRoYXQgYSB0d28tZW5naW5lIHBsYW5lIG11c3QgYWx3YXlzIGJlIHdpdGhpbiA2MCBtaW51dGVzIG9mIHRoZSBuZWFyZXN0IGFkZXF1YXRlIGFpcnBvcnQgYWxvbmcgaXRzIGVudGlyZSBcdWZiMDJpZ2h0IHBhdGguIEEgdmFyaWV0eSBvZiBzaW1pbGFyIHJ1bGVzIGhhdmUgZXhpc3RlZCwgYnV0IGF0IHRoZWlyIGNvcmUsIHRoZXkgcmVtYWluIHRoZSBzYW1lOiB0aGUgXHVmYjAyaWdodCBwYXRoIGNhbiBub3QgdGFrZSB0aGUgYWlycGxhbmUgbW9yZSB0aGFuIGEgY2VydGFpbiBtYXhpbXVtIGFsbG93ZWQgZGlzdGFuY2UgZnJvbSB0aGUgbmVhcmVzdCBhaXJwb3J0LiBXaXRoIHRoZXNlIHJlc3RyaWN0aW9ucywgcGxhbmVzIGNhbm5vdCBhbHdheXMgdXNlIGEgZGlyZWN0IHJvdXRlIGZvciBcdWZiMDJ5aW5nIGZyb20gb25lIGFpcnBvcnQgdG8gYW5vdGhlci48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtIHdlIHdpbGwgY29tcHV0ZSB0aGUgc2hvcnRlc3QgXHVmYjAyaWdodCBwYXRoIGJldHdlZW4gdHdvIGFpcnBvcnRzIHdoaWxlIGFkaGVyaW5nIHRvIGEgbWF4aW11bSBhbGxvd2VkIGRpc3RhbmNlIHJ1bGUuIEluIHRoZSBcdWZiMDFndXJlIGJlbG93LCB3aGljaCBpbGx1c3RyYXRlcyB0aGUgXHVmYjAxcnN0IHNhbXBsZSB0ZXN0IGNhc2UsIGFueSBcdWZiMDJpZ2h0IHJvdXRlIGhhcyB0byBzdGF5IHdpdGhpbiB0aGUgdGhyZWUgY2lyY2xlcy4gVGh1cyBhIHBsYW5lIGdvaW5nIGZyb20gYWlycG9ydCAyIHRvIGFpcnBvcnQgMyBoYXMgdG8gZGV0b3VyIGZyb20gdGhlIGRpcmVjdCByb3V0ZSB2aWEgdGhlIHJlZ2lvbiBhcm91bmQgYWlycG9ydCAxLiBOb3RlIHRoYXQgdGhlIHBsYW5lIHdvdWxkIG5vdCBuZWNlc3NhcmlseSBoYXZlIHRvIGdvIHRvIGFpcnBvcnQgMSBpdHNlbGYuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2ZwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM0MXB4OyB3aWR0aDozODBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGluZ3MgYXJlIGZ1cnRoZXIgY29tcGxpY2F0ZWQgYnkgdGhlIGZhY3QgdGhhdCBwbGFuZXMgaGF2ZSBsaW1pdGVkIGZ1ZWwgc3VwcGx5LCBhbmQgdG8gZ28gbG9uZ2VyIGRpc3RhbmNlcyB0aGV5IG1heSBuZWVkIHRvIG1ha2UgYSBzdG9wb3ZlciBhdCBpbnRlcm1lZGlhdGUgYWlycG9ydHMuIFRodXMsIGRlcGVuZGluZyBvbiB0aGUgZnVlbCBjYXBhY2l0eSwgYSBwbGFuZSBnb2luZyBmcm9tIGFpcnBvcnQgMiB0byBhaXJwb3J0IDMgaW4gdGhlIFx1ZmIwMWd1cmUgbWlnaHQgaGF2ZSB0byBzdG9wIG92ZXIgYXQgYWlycG9ydCAxIChvciB0aGUgZnVlbCBjYXBhY2l0eSBtaWdodCBiZSB0b28gbG93IGV2ZW4gdG8gZ28gdG8gYWlycG9ydCAxLCBpbiB3aGljaCBjYXNlIHRoZSB0cmlwIHdvdWxkIGJlIGltcG9zc2libGUgdG8gbWFrZSkuPFwvcD5cclxuXHJcbjxwPldlIG1ha2UgdGhlIGZvbGxvd2luZyBzaW1wbGlmeWluZyBhc3N1bXB0aW9uczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGUgc3VyZmFjZSZuYnNwO29mIHRoZSBlYXJ0aCBpcyBhIHNwaGVyZSBvZiByYWRpdXMgNjM3MCBrbS48XC9saT5cclxuXHQ8bGk+Qm90aCB0aW1lIGFuZCBmdWVsIGNvbnN1bXB0aW9uIGFyZSBkaXJlY3RseSBwcm9wb3J0aW9uYWwgdG8gZGlzdGFuY2UgdHJhdmVsZWQuIEluIG90aGVyIHdvcmRzIHdlIGFyZSBpbnRlcmVzdGVkIG9ubHkgaW4gdG90YWwgZGlzdGFuY2UgdHJhdmVsZWQuPFwvbGk+XHJcblx0PGxpPlRoZSBkaWZmZXJlbmNlIGluIGRpc3RhbmNlIGNhdXNlZCBieSBwbGFuZXMgXHVmYjAyeWluZyBhdCBkaWZmZXJlbnQgYWx0aXR1ZGVzIGlzIG5lZ2xpZ2libGUuIFRodXMsIGVmZmVjdGl2ZWx5LCB3ZSBhc3N1bWUgdGhlbSB0byBiZSBcdWZiMDJ5aW5nIGFsb25nIHRoZSBlYXJ0aCZyc3F1bztzIHN1cmZhY2UuPFwvbGk+XHJcblx0PGxpPkEgcGxhbmUgbWF5Jm5ic3A7c3RvcCBmb3IgcmVmdWVsaW5nIGF0IGFzIG1hbnkgaW50ZXJtZWRpYXRlIGFpcnBvcnRzIGFzIG5lZWRlZCwgZWFjaCB0aW1lIGdldHRpbmcgYSBmdWxsIHRhbmsuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgUiwgd2hlcmUgMiAmbGU7IE4gJmxlOyAyNSBpcyB0aGUgbnVtYmVyIG9mIGFpcnBvcnRzIGFuZCAxICZsZTsgUiAmbGU7IDEwIDAwMCBpcyB0aGUgbWF4aW11bSBhbGxvd2VkIFx1ZmIwMmlnaHQgZGlzdGFuY2UgKGluIGttKSBmcm9tIHRoZSBuZWFyZXN0IGFpcnBvcnQuIEVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgJlBoaTssICZ0aGV0YTsgc2F0aXNmeWluZyAwICZsZTsgJlBoaTsgJmx0OyAzNjAgYW5kIC05MCAmbGU7ICZ0aGV0YTsgJmxlOyA5MCwgdGhlIGxvbmdpdHVkZSBhbmQgbGF0aXR1ZGUgKHJlc3BlY3RpdmVseSkgb2YgYW4gYWlycG9ydCwgaW4gZGVncmVlcy4gVGhlIGFpcnBvcnRzIGFyZSBudW1iZXJlZCBhY2NvcmRpbmcgdG8gdGhlaXIgb3JkZXIgaW4gdGhlIGlucHV0IHN0YXJ0aW5nIGZyb20gb25lLiBObyB0d28gYWlycG9ydHMgYXJlIGF0IHRoZSBzYW1lIHBvc2l0aW9uLjxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgdGhpcyBpcyBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIFEsIHNhdGlzZnlpbmcgMSAmbGU7IFEgJmxlOyAxMDAuIEVhY2ggb2YgdGhlIG5leHQgUSBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBzLCB0LCBjIHNhdGlzZnlpbmcgMSAmbGU7IHM7IHQgJmxlOyBOLCBzICZuZTsgdCwgYW5kIDEgJmxlOyBjICZsZTsgNTAgMDAwLCBpbmRpY2F0aW5nIGEgcGxhbmUgZ29pbmcgZnJvbSBhaXJwb3J0IHMgdG8gYWlycG9ydCB0IHdpdGggYSBmdWVsIGNhcGFjaXR5IHlpZWxkaW5nIGEgcmFuZ2Ugb2YgYyBrbS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgdGhlIGNhc2UgbnVtYmVyIGZvbGxvd2VkIGJ5IG9uZSBsaW5lIGZvciBlYWNoIHF1ZXJ5IGNvbnRhaW5pbmcgdGhlIGxlbmd0aCBpbiBrbSBvZiB0aGUgc2hvcnRlc3QgXHVmYjAyaWdodCBwYXRoIGJldHdlZW4gYWlycG9ydCBzIGFuZCB0LCBzdWJqZWN0IHRvIHRoZSBmdWVsIGNvbnN0cmFpbnQgYy4gRGlzcGxheSB0aGUgbGVuZ3RoIGFjY3VyYXRlIHRvIHRocmVlIGRlY2ltYWwgcGxhY2VzLiBJZiB0aGVyZSBpcyBubyBwZXJtaXNzaWJsZSBwYXRoIGJldHdlZW4gdGhlIHR3byBhaXJwb3J0cywgdGhlbiBkaXNwbGF5IHRoZSB3b3JkIGltcG9zc2libGUgaW5zdGVhZC48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhlIGFuc3dlciBpcyBudW1lcmljYWxseSBzdGFibGUgZm9yIHBlcnR1cmJhdGlvbnMgb2YgdXAgdG8gMDoxIGttIG9mIFIgb3IgYy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: lll4592