시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 19 7 4 36.364%

문제

작년에 알고스팟 운영진들은 ACM-ICPC 대전 대회에 가기 위해 기차를 타고 이동했다. 하지만, 이것은 곧 엄청난 재앙으로 이어졌다. 대전으로 갈 때는 대전역에 발생한 불로 인해 열차가 지연되었고, 서울로 돌아올 때는 서울에 대한 테러 위협때문에 기차가 엄청나게 지연되었다. 이러한 엄청난 열차의 지연은 다른 열차도 지연되게 만든다. 느린 열차를 타는 것과 급행 열차를 기다리는 것 중 어떤 것이 열차가 지연될 확률이 적을까?

올해 알고스팟 운영진들은 열차 스케줄을 분석하고 계획을 세우기로 했다. 그들은 기차가 얼마나 지연되고, 얼마나 자주 지연되는지를 조사했다. 이제 이 정보를 가지고 이동 시간의 기대값이 가장 작은 열차를 타려고 한다.

각각의 열차에 대해서 알고스팟 운영진은 출발 시간과 소요 시간을 정확하게 알고 있다. 또, 그 열차가 지연될 확률도 알고 있다. 열차가 지연될 확률은 독립이고, 가는 도중에 지연되는 열차가 발생하면, 그 지연을 반영해서 여행 계획을 바꿀 수 있다.

열차는 항상 정시에 출발한다. 하지만, 도착 시간은 지연될 수 있다. 알고스팟 운영진은 열차가 지연될지 말지를 열차가 출발하기 전까지 알 수 없다. 알고스팟 운영진이 열차를 환승하는데 드는 시간은 0이다. 따라서, 열차가 도착한 시간과 동시에 출발하는 시간의 열차를 탈 수 있다.

알고스팟 운영진은 첫 기차를 타는 시간을 마음대로 정할 수 있다. 기차를 타고 이동하는데 드는 시간의 기대값의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 출발 도시의 이름과 도착 도시의 이름이 주어진다. 출발 도시와 도착 도시의 이름이 같은 경우는 없다. 그 다음 줄에는 열차의 수 n (1 ≤ n ≤ 1000)이 주어진다. 다음 n개의 줄에는 한 줄에 하나씩 열차의 정보가 주어진다.

열차의 정보는 다음과 같이 구성되어져 있다.

  • 출발 도시와 도착 도시. 두 도시의 이름이 같은 경우는 없다.
  • 열차의 출발 시간 m (0 ≤ m ≤ 59). 열차는 항상 1시간에 한 편씩 있으며, m분에 출발한다.
  • 열차의 소요 시간 t ( 1 ≤ t ≤ 300). 열차가 지연되지 않았을 때 걸리는 시간이다.
  • 열차가 지연될 퍼센트 확률 p (0 ≤ p ≤ 100).
  • 열차의 최대 지연 시간 d (1 ≤ d ≤ 120). d의 단위는 분이다.

모든 도시의 이름은 알파벳 대문자와 소문자로만 이루어져 있으며, 길이는 20을 넘지 않는다. 열차는 항상 정수 분 만큼 지연되며, 확률은 구간 [1, d]에 균일하게 분포되어 있다.

출력

각 테스트 케이스에 대해서 여행을 하는데 걸리는 시간의 기대값의 최소값을 출력한다.

만약, 도착 도시에 갈 수 없는 경우에는 "IMPOSSIBLE"을 출력하며, 소수점 오차는 10-6까지 허용한다.

예제 입력 1

3
Seoul Daejeon
3
Seoul Daejeon 15 68 10 5
Seoul Daejeon 46 55 50 60
Daejeon Busan 14 226 10 120
Seoul Daejeon
1
Seoul Busan 10 22 5 10
Seoul Daejeon
9
Seoul Gwangmyeong 15 10 0 1
Seoul Gwangmyeong 45 10 0 1
Seoul Cheonan 23 140 10 15
Gwangmyeong Busan 44 51 60 70
Busan Incheon 55 147 38 40
Incheon Daejeon 24 15 30 15
Incheon Daejeon 54 15 10 35
Cheonan Anyang 45 140 5 10
Anyang Incheon 46 96 10 20

예제 출력 1

68.3
IMPOSSIBLE
305.0532857

힌트

첫 번재 예제에서 서울에서 대전으로 이동할 때, 느린 열차를 타는 것이 더 좋다. 빠른 열차의 소요 시간의 기대값은 70.25분이다.

W3sicHJvYmxlbV9pZCI6IjM2NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjRcdWNjMjggXHVjOWMwXHVjNWYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3OTFcdWIxNDRcdWM1ZDAgXHVjNTRjXHVhY2UwXHVjMmE0XHVkMzFmIFx1YzZiNFx1YzYwMVx1YzljNFx1YjRlNFx1Yzc0MCBBQ00tSUNQQyBcdWIzMDBcdWM4MDQgXHViMzAwXHVkNjhjXHVjNWQwIFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZTMwXHVjYzI4XHViOTdjIFx1ZDBjMFx1YWNlMCBcdWM3NzRcdWIzZDlcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0XHVhYzgzXHVjNzQwIFx1YWNlNyBcdWM1YzRcdWNjYWRcdWIwOWMgXHVjN2FjXHVjNTU5XHVjNzNjXHViODVjIFx1Yzc3NFx1YzViNFx1Yzg0Y1x1YjJlNC4gXHViMzAwXHVjODA0XHVjNzNjXHViODVjIFx1YWMwOCBcdWI1NGNcdWIyOTQgXHViMzAwXHVjODA0XHVjNWVkXHVjNWQwIFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWJkODhcdWI4NWMgXHVjNzc4XHVkNTc0IFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWM5YzBcdWM1ZjBcdWI0MThcdWM1YzhcdWFjZTAsIFx1YzExY1x1YzZiOFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MmMgXHViNTRjXHViMjk0IFx1YzExY1x1YzZiOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVkMTRjXHViN2VjIFx1YzcwNFx1ZDYxMVx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFlMzBcdWNjMjhcdWFjMDAgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1YzljMFx1YzVmMFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzVjNFx1Y2NhZFx1YjA5YyBcdWM1ZjRcdWNjMjhcdWM3NTggXHVjOWMwXHVjNWYwXHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWM1ZjRcdWNjMjhcdWIzYzQgXHVjOWMwXHVjNWYwXHViNDE4XHVhYzhjIFx1YjljY1x1YjRlMFx1YjJlNC4gXHViMjkwXHViOWIwIFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWQwYzBcdWIyOTQgXHVhYzgzXHVhY2ZjIFx1YWUwOVx1ZDU4OSBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVhZTMwXHViMmU0XHViOWFjXHViMjk0IFx1YWM4MyBcdWM5MTEgXHVjNWI0XHViNWE0IFx1YWM4M1x1Yzc3NCBcdWM1ZjRcdWNjMjhcdWFjMDAgXHVjOWMwXHVjNWYwXHViNDIwIFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWM4MDFcdWM3NDRcdWFlNGM/PFwvcD5cclxuXHJcbjxwPlx1YzYyY1x1ZDU3NCBcdWM1NGNcdWFjZTBcdWMyYTRcdWQzMWYgXHVjNmI0XHVjNjAxXHVjOWM0XHViNGU0XHVjNzQwIFx1YzVmNFx1Y2MyOCBcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDQgXHViZDg0XHVjMTFkXHVkNTU4XHVhY2UwIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWMxMzhcdWM2YjBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVhZTMwXHVjYzI4XHVhYzAwIFx1YzViY1x1YjljOFx1YjA5OCBcdWM5YzBcdWM1ZjBcdWI0MThcdWFjZTAsIFx1YzViY1x1YjljOFx1YjA5OCBcdWM3OTBcdWM4ZmMgXHVjOWMwXHVjNWYwXHViNDE4XHViMjk0XHVjOWMwXHViOTdjIFx1Yzg3MFx1YzBhY1x1ZDU4OFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1Yzc3NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc3NFx1YjNkOSBcdWMyZGNcdWFjMDRcdWM3NTggXHVhZTMwXHViMzAwXHVhYzEyXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjNWY0XHVjYzI4XHViOTdjIFx1ZDBjMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM1ZjRcdWNjMjhcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzU0Y1x1YWNlMFx1YzJhNFx1ZDMxZiBcdWM2YjRcdWM2MDFcdWM5YzRcdWM3NDAgXHVjZDljXHViYzFjIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWMxOGNcdWM2OTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YWRmOCBcdWM1ZjRcdWNjMjhcdWFjMDAgXHVjOWMwXHVjNWYwXHViNDIwIFx1ZDY1NVx1Yjk2MFx1YjNjNCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM1ZjRcdWNjMjhcdWFjMDAgXHVjOWMwXHVjNWYwXHViNDIwIFx1ZDY1NVx1Yjk2MFx1Yzc0MCBcdWIzYzVcdWI5YmRcdWM3NzRcdWFjZTAsIFx1YWMwMFx1YjI5NCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHVjOWMwXHVjNWYwXHViNDE4XHViMjk0IFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NThcdWJhNzQsIFx1YWRmOCBcdWM5YzBcdWM1ZjBcdWM3NDQgXHViYzE4XHVjNjAxXHVkNTc0XHVjMTFjIFx1YzVlY1x1ZDU4OSBcdWFjYzRcdWQ2OGRcdWM3NDQgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVmNFx1Y2MyOFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjODE1XHVjMmRjXHVjNWQwIFx1Y2Q5Y1x1YmMxY1x1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIzYzRcdWNjMjkgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzljMFx1YzVmMFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1NGNcdWFjZTBcdWMyYTRcdWQzMWYgXHVjNmI0XHVjNjAxXHVjOWM0XHVjNzQwIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWM5YzBcdWM1ZjBcdWI0MjBcdWM5YzAgXHViOWQwXHVjOWMwXHViOTdjIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWNkOWNcdWJjMWNcdWQ1NThcdWFlMzAgXHVjODA0XHVhZTRjXHVjOWMwIFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM1NGNcdWFjZTBcdWMyYTRcdWQzMWYgXHVjNmI0XHVjNjAxXHVjOWM0XHVjNzc0IFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWQ2NThcdWMyYjlcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAwXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWIzYzRcdWNjMjlcdWQ1NWMgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWNkOWNcdWJjMWNcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWQwYzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHVhY2UwXHVjMmE0XHVkMzFmIFx1YzZiNFx1YzYwMVx1YzljNFx1Yzc0MCBcdWNjYWIgXHVhZTMwXHVjYzI4XHViOTdjIFx1ZDBjMFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHViOWM4XHVjNzRjXHViMzAwXHViODVjIFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFlMzBcdWNjMjhcdWI5N2MgXHVkMGMwXHVhY2UwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1YWUzMFx1YjMwMFx1YWMxMlx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMTAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDljXHViYzFjIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWFjZmMgXHViM2M0XHVjYzI5IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNkOWNcdWJjMWMgXHViM2M0XHVjMmRjXHVjNjQwIFx1YjNjNFx1Y2MyOSBcdWIzYzRcdWMyZGNcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZjRcdWNjMjhcdWM3NTggXHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2Q5Y1x1YmMxYyBcdWIzYzRcdWMyZGNcdWM2NDAgXHViM2M0XHVjYzI5IFx1YjNjNFx1YzJkYy4gXHViNDUwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWNkOWNcdWJjMWMgXHVjMmRjXHVhYzA0IG0gKDAgJmxlOyBtICZsZTsgNTkpLiBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVkNTZkXHVjMGMxIDFcdWMyZGNcdWFjMDRcdWM1ZDAgXHVkNTVjIFx1ZDNiOFx1YzUyOSBcdWM3ODhcdWM3M2NcdWJhNzAsIG1cdWJkODRcdWM1ZDAgXHVjZDljXHViYzFjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1ZjRcdWNjMjhcdWM3NTggXHVjMThjXHVjNjk0IFx1YzJkY1x1YWMwNCB0ICggMSAmbGU7IHQgJmxlOyAzMDApLiBcdWM1ZjRcdWNjMjhcdWFjMDAgXHVjOWMwXHVjNWYwXHViNDE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1Yzc0NCBcdWI1NGMgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNWY0XHVjYzI4XHVhYzAwIFx1YzljMFx1YzVmMFx1YjQyMCBcdWQzN2NcdWMxM2NcdWQyYjggXHVkNjU1XHViOTYwIHAgKDAgJmxlOyBwICZsZTsgMTAwKS48XC9saT5cclxuXHQ8bGk+XHVjNWY0XHVjYzI4XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWM5YzBcdWM1ZjAgXHVjMmRjXHVhYzA0IGQgKDEgJmxlOyBkICZsZTsgMTIwKS4gZFx1Yzc1OCBcdWIyZThcdWM3MDRcdWIyOTQgXHViZDg0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM2NDAgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAyMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgxNVx1YzIxOCBcdWJkODQgXHViOWNjXHVkMDdjIFx1YzljMFx1YzVmMFx1YjQxOFx1YmE3MCwgXHVkNjU1XHViOTYwXHVjNzQwIFx1YWQ2Y1x1YWMwNCBbMSwgZF1cdWM1ZDAgXHVhZGUwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YmQ4NFx1ZDNlY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWFlMzBcdWIzMDBcdWFjMTJcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjXHVjNWQwIFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHVjMThjXHVjMjE4XHVjODEwIFx1YzYyNFx1Y2MyOFx1YjI5NCAxMDxzdXA+LTY8XC9zdXA+XHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzdhYyBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjMTFjXHVjNmI4XHVjNWQwXHVjMTFjIFx1YjMwMFx1YzgwNFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWIyOTBcdWI5YjAgXHVjNWY0XHVjYzI4XHViOTdjIFx1ZDBjMFx1YjI5NCBcdWFjODNcdWM3NzQgXHViMzU0IFx1Yzg4Ylx1YjJlNC4gXHViZTYwXHViOTc4IFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWMxOGNcdWM2OTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1YWUzMFx1YjMwMFx1YWMxMlx1Yzc0MCA3MC4yNVx1YmQ4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmFpbiBkZWxheXMiLCJkZXNjcmlwdGlvbiI6IjxwPkxhc3QgeWVhciwgc29tZSBvZiB0aGUganVkZ2VzIHRyaWVkIHRvIHRyYXZlbCB0byBOV0VSQyZyc3F1bzsxMCBieSB0cmFpbi4gVGhpcyB0dXJuZWQgaW50byBhIGJpZyBkaXNhc3Rlcjogb24gdGhlIHdheSB0aGVyZSwgYSBcdWZiMDFyZSBpbiBhIGNvbnRyb2wgcm9vbSBjYXVzZWQgaHVnZSBkZWxheXMsIHdoaWxlIG9uIHRoZSByZXR1cm4gdHJpcCwgdHJhaW5zIGluIEJyZW1lbiB3ZXJlIGRlbGF5ZWQgZHVlIHRvIGEgdGVycm9yaXN0IHRocmVhdCBpbiBIYW1idXJnLiBPZiBjb3Vyc2UsIHRoZXNlIGh1Z2UgZGVsYXlzIGNhdXNlZCBvdGhlciBkZWxheXMgaW4gdGhlIHRyYWluIHNjaGVkdWxlLCBzbyB0aGUgYmlnIHF1ZXN0aW9uIHdhcyB3aGljaCB0cmFpbnMgdG8gdGFrZTogd291bGQgaXQgYmUgYmV0dGVyIHRvIHRha2UgdGhpcyBzbG93IHJlZ2lvbmFsIHRyYWluIG5vdywgb3Igd2FpdCBmb3IgdGhhdCBpbnRlcmNpdHkgdHJhaW4sIHdoaWNoIGhhcyBhIGJpZyBjaGFuY2Ugb2YgYmVpbmcgZGVsYXllZD88XC9wPlxyXG5cclxuPHA+VGhpcyB5ZWFyLCB0aGUganVkZ2VzIGhhdmUgcGxhbm5lZCBhaGVhZCBhbmQgY2FyZWZ1bGx5IGFuYWx5emVkIHRoZSB0cmFpbiBzY2hlZHVsZS4gVGhleSBldmVuIGtlcHQgdHJhY2sgb2YgaG93IG9mdGVuIHRyYWlucyB3ZXJlIGRlbGF5ZWQgYW5kIGJ5IGhvdyBtdWNoLiBOb3cgdGhhdCB0aGV5IGhhdmUgYWxsIHRoaXMgaW5mb3JtYXRpb24sIHRoZXkgd2FudCB0byB0cmF2ZWwgYXMgcXVpY2tseSBwb3NzaWJsZSwgbWluaW1pemluZyB0aGUgZXhwZWN0ZWQgZHVyYXRpb24gb2YgdGhlIGpvdXJuZXkuIENhbiB5b3UgaGVscCB0aGVtPzxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB0cmFpbiBjb25uZWN0aW9uLCB0aGUganVkZ2VzIGtub3cgZXhhY3RseSB3aGF0IGl0cyBzY2hlZHVsZWQgZGVwYXJ0dXJlIHRpbWUgYW5kIGR1cmF0aW9uIGFyZSwgYXMgd2VsbCBhcyB0aGUgcHJvYmFiaWxpdHkgdGhhdCBpdHMgYXJyaXZhbCBhdCB0aGUgZGVzdGluYXRpb24gd2lsbCBiZSBkZWxheWVkLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBwcm9iYWJpbGl0aWVzIG9mIGRlbGF5cyBhcmUgaW5kZXBlbmRlbnQgYW5kIHRoYXQgdGhlIGp1ZGdlcyBjYW4gYWRhcHQgdGhlaXIgaXRpbmVyYXJ5IGFzIHRoZXkgZ28sIGRlcGVuZGluZyBvbiBhbnkgZGVsYXlzIHdoaWNoIHRoZXkgbWlnaHQgYWxyZWFkeSBoYXZlIGluY3VycmVkLiBUcmFpbnMgYWx3YXlzIGRlcGFydCBvbiB0aW1lLCBidXQgbWF5IGFycml2ZSBsYXRlIGFuZCB0aGUganVkZ2VzIGRvIG5vdCBrbm93IHdoZXRoZXIgYSB0cmFpbiZyc3F1bztzIGFycml2YWwgd2lsbCBiZSBkZWxheWVkIHVudGlsIHRoZXkgaGF2ZSBib2FyZGVkIGl0LiBJdCB0YWtlcyBqdWRnZXMgbm8gdGltZSB0byBzd2l0Y2ggdHJhaW5zLCBzbyB0aGV5IGNhbiB0YWtlIGEgY29ubmVjdGluZyB0cmFpbiB0aGF0IGRlcGFydHMgYXQgdGhlIHNhbWUgdGltZSBhcyB0aGV5IGFycml2ZSBhdCBhIHBsYWNlLjxcL3A+XHJcblxyXG48cD5UaGUganVkZ2VzIGNhbiBjaG9vc2UgdGhlIHRpbWUgb2YgdGhlaXIgaW5pdGlhbCBkZXBhcnR1cmUgYXMgdGhleSB3aXNoIGFuZCB0aGV5IHdhbnQgdG8gbWluaW1pemUgdGhlIGV4cGVjdGVkIGR1cmF0aW9uIG9mIHRoZWlyIHRvdGFsIHRyaXAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgYSBwb3NpdGl2ZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0aGUganVkZ2VzJnJzcXVvOyBwbGFjZSBvZiBvcmlnaW4gYW5kIGRlc3RpbmF0aW9uLCB0aGVzZSBhcmUgZGlmZmVyZW50LjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2YgdHJhaW4gY29ubmVjdGlvbnMuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMsIGVhY2ggZGVzY3JpYmluZyBhIHRyYWluIGNvbm5lY3Rpb246PFwvbGk+XHJcblx0PGxpPnRoZSBvcmlnaW4gYW5kIGRlc3RpbmF0aW9uIG9mIHRoaXMgY29ubmVjdGlvbiwgdGhlc2UgYXJlIGRpZmZlcmVudC5cclxuXHQ8dWw+XHJcblx0XHQ8bGk+YW4gaW50ZWdlciBtICgwICZsZTsgbSAmbGU7IDU5KSwgdGhlIGRlcGFydHVyZSB0aW1lIGluIG1pbnV0ZXMgYWZ0ZXIgZWFjaCBmdWxsIGhvdXIuPFwvbGk+XHJcblx0XHQ8bGk+YW4gaW50ZWdlciB0ICgxICZsZTsgdCAmbGU7IDMwMCksIHRoZSBzdGFuZGFyZCBqb3VybmV5IHRpbWUgKGFzc3VtaW5nIG5vIGRlbGF5cykuPFwvbGk+XHJcblx0XHQ8bGk+YW4gaW50ZWdlciBwICgwICZsZTsgcCAmbGU7IDEwMCksIHRoZSBwcm9iYWJpbGl0eSBvZiBkZWxheXMgYXMgYSBwZXJjZW50YWdlLjxcL2xpPlxyXG5cdFx0PGxpPmFuIGludGVnZXIgZCAoMSAmbGU7IGQgJmxlOyAxMjApLCB0aGUgbWF4aW11bSBkZWxheSBpbiBtaW51dGVzLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsbCBwbGFjZSBuYW1lcyBhcmUgZ2l2ZW4gYXMgc3RyaW5ncyBvZiB1cHBlciBhbmQgbG93ZXIgY2FzZSBhbHBoYWJldGljYWwgY2hhcmFjdGVycywgb2YgbGVuZ3RoIGF0IG1vc3QgMjAuIElmIGEgdHJhaW4gaXMgZGVsYXllZCwgdGhlbiB0aGUgbGVuZ3RoIG9mIHRoZSBkZWxheSB3aWxsIGJlIGEgd2hvbGUgbnVtYmVyIG9mIG1pbnV0ZXMsIGFuZCB3aWxsIGJlIHVuaWZvcm1seSBkaXN0cmlidXRlZCBpbiB0aGUgcmFuZ2UgWzEsIGRdLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXI6IHRoZSBtaW5pbXVtIGV4cGVjdGVkIGR1cmF0aW9uIG9mIHRoZSB0b3RhbCB0cmlwIGluIG1pbnV0ZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhpcyBudW1iZXIgc2hvdWxkIGJlIGFjY3VyYXRlIHVwIHRvIDEwPHN1cD4tNjxcL3N1cD4gcmVsYXRpdmUgb3IgYWJzb2x1dGUgcHJlY2lzaW9uLiBPdXRwdXQgSU1QT1NTSUJMRSBpbnN0ZWFkIGlmIHRoZSBkZXN0aW5hdGlvbiBpcyBub3QgcmVhY2hhYmxlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5vdGUgaW4gdGhlIFx1ZmIwMXJzdCBleGFtcGxlIHRoYXQgaXQgaXMgYmV0dGVyIHRvIHRha2UgdGhlIHNsb3dlciB0cmFpbiBmcm9tIFNlb3VsIHRvIERhZWplb24sIHNpbmNlIHRoZSBmYXN0IHRyYWluIHdvdWxkIGdpdmUgYW4gZXhwZWN0ZWQgdHJhdmVsIHRpbWUgb2YgNzA6MjUgbWludXRlcy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 J번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kipa00