시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB6965131074615.689%

문제

오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다.

상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이전)에 평행 우주의 다른 구멍에서 나오게 된다. 

묘지는 W × H 크기의 그리드로 나타낼 수 있다. 묘지의 입구는 (0, 0)이고, 출구는 (W-1, H-1)이다. 상근이는 겁이 많기 때문에, 최대한 빨리 묘지를 나가려고 한다. 그리고 상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다. 상근이는 현재 있는 칸과 동, 서, 남, 북으로 인접한 칸으로 이동할 수 있다. 각 칸은 잔디, 묘비, 또는 귀신 구멍이다.

  • 묘비는 매우 높기 때문에, 묘비가 있는 칸으로는 이동할 수 없다.
  • 귀신 구멍이 있는 칸으로 이동하면, 특정 시간이 지난 후에 묘지의 다른 곳에서 상근이가 나타나게 된다. 시간은 귀신 구멍마다 다르며, 양수, 음수, 0 중 하나이다.
  • 잔디가 있는 칸으로는 자유롭게 이동할 수 있다.

상근이는 묘지를 빨리 나가기 위해 귀신 구멍도 이용할 것이다. 묘지를 나갈 수 없는 경우나, 계속해서 과거로 이동하는 경우가 존재할 수도 있다.

묘지가 위와 같이 생긴 경우(문제의 두 번째 예제)를 살펴보자. 묘비는 (2,1)와 (3,1)에 있고, 귀신 구멍은 0초만에 (3,0)로 들어가서 (2,2)에서 나오는 구멍 하나가 있다. 묘지를 빠져나오는데 걸리는 가장 빠른 시간은 4초이며, 다음과 같다.

(0,0) -> 동(1초) (1,0) -> 동(1초) (2,0) -> 동(1초) (3,0) -> 귀신구멍(0초) (2,2) -> 동(1초) (3,2)

귀신 구멍을 이용하지 않는다면 가장 빠른 시간은 5초이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 묘지의 너비 W와 높이 H가 주어진다. (1 ≤ W, H ≤ 30) 다음 줄에는 묘비의 개수 G (G ≥ 0)가 주어진다. 다음 G개 줄에는 묘비의 위치를 나타내는 두 정수 X와 Y가 주어진다. (0 ≤ X < W, 0 ≤ Y < H)

다음 줄에는 귀신 구멍의 수 E (E ≥ 0)가 주어진다. 다음 E개 줄에는 귀신 구멍의 정보를 나타내는 X1, Y1, X2, Y2, T 가 주어진다. (X1, Y1)은 귀신 구멍의 위치이고, (X2, Y2)는 그 귀신 구멍으로 들어갔을 때, 나오는 곳의 위치이다. (0 ≤ X1, X2 < W, 0 ≤ Y1, Y2 < H) (X1,Y1)과 (X2,Y2)가 같을 수도 있다. T는 귀신 구멍에서 나오는데 걸리는 시간이다. (-10,000 ≤ T ≤ 10,000) T가 양수인 경우에는 귀신 구멍을 들어간 이후에 나온다는 의미이다. 두 귀신 구멍이 같은 장소에 있거나, 구멍에서 나오는 지점이 묘비인 경우는 없다. 묘비와 귀신 구멍이 (0, 0)이나 (W-1, H-1)에 있는 경우는 없다.

입력의 마지막 줄에는 0 0이 주어진다.

출력

각 테스트 케이스 마다 상근이가 과거로 계속해서 돌아간다면 "Never"를 출력하고, 출구를 빠져나올 수 없으면 "Impossible"을 출력한다. 그 외의 경우에는 묘지를 빠져나오는데 가장 빠른 시간을 출력한다.

예제 입력 1

3 3
2
2 1
1 2
0
4 3
2
2 1
3 1
1
3 0 2 2 0
4 2
0
1
2 0 1 0 -3
0 0

예제 출력 1

Impossible
4
Never
W3sicHJvYmxlbV9pZCI6IjM4NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjBcdWI4NWNcdWM3MDggXHViYjE4XHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVkNTYwXHViODVjXHVjNzA4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1ZDU2MFx1Yjg1Y1x1YzcwOFx1Yzc0NCBcdWFlMzBcdWIxNTBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmIxOFx1YzljMFx1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHVkNTVjIFx1YmE4NVx1YzUyOSBcdWJiMThcdWM5YzBcdWI4NWMgXHViNGU0XHVjNWI0XHVhYzAwXHVhY2UwLCBcdWQ2M2NcdWM3OTBcdWMxMWMgXHViYjE4XHVjOWMwXHVjNzU4IFx1Y2Q5Y1x1YWQ2Y1x1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM4MWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWNjMjhcdWI4NDBcdWFjMDAgXHViM2NjXHVjNTQ0XHVjNjU0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNWI0XHViODM4XHVjNzQ0IFx1YzgwMVx1YzVkMCBcdWQ1NjBcdWJhMzhcdWIyYzhcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1ZDU2MFx1Yjg1Y1x1YzcwOCBcdWJjMjRcdWM1ZDAgXHViYjE4XHVjOWMwXHVjNWQwXHViMjk0IFx1YWRjMFx1YzJlMCBcdWFkNmNcdWJhNGRcdWM3NzQgXHViMDk4XHVkMGMwXHViMDljXHViMmU0XHVhY2UwIFx1YjlkMFx1ZDU3NFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVhZGMwXHVjMmUwIFx1YWQ2Y1x1YmE0ZFx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQsIFx1YmIxOFx1YzljMFx1Yzc1OCBcdWIyZTRcdWI5NzggXHVjN2E1XHVjMThjXHViODVjIFx1YjJlNFx1YzJkYyBcdWIwOThcdWM2MjRcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzQgXHVhZDZjXHViYTRkXHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWJhNGRcdWM3NzRcdWIyZTQuIFx1YWRjMFx1YzJlMCBcdWFkNmNcdWJhNGRcdWM1ZDAgXHViNWE4XHVjNWI0XHVjOWMwXHViYTc0LCBcdWQyYjlcdWM4MTUgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzljMFx1YjA5YyBcdWQ2YzQoXHViNjEwXHViMjk0IFx1Yzc3NFx1YzgwNClcdWM1ZDAgXHVkM2M5XHVkNTg5IFx1YzZiMFx1YzhmY1x1Yzc1OCBcdWIyZTRcdWI5NzggXHVhZDZjXHViYTRkXHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmIxOFx1YzljMFx1YjI5NCBXICZ0aW1lczsgSCBcdWQwNmNcdWFlMzBcdWM3NTggXHVhZGY4XHViOWFjXHViNGRjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJiMThcdWM5YzBcdWM3NTggXHVjNzg1XHVhZDZjXHViMjk0ICgwLCAwKVx1Yzc3NFx1YWNlMCwgXHVjZDljXHVhZDZjXHViMjk0IChXLTEsIEgtMSlcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjODFcdWM3NzQgXHViOWNlXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmU2OFx1YjlhYyBcdWJiMThcdWM5YzBcdWI5N2MgXHViMDk4XHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIzNTggXHViM2M0XHVjOTExIFx1Y2Q5Y1x1YWQ2Y1x1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NThcdWJhNzQgXHViNGE0XHViM2M0IFx1YjNjY1x1YzU0NFx1YmNmNFx1YzljMCBcdWM1NGFcdWFjZTAgXHVhZGY4IFx1Yzk4OVx1YzJkYyBcdWJiMThcdWM5YzBcdWI5N2MgXHViZTYwXHVjODM4XHViMDk4XHVhYzA4IFx1YzBkZFx1YWMwMVx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1YjNkOSwgXHVjMTFjLCBcdWIwYTgsIFx1YmQ4MVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1Yzc5NFx1YjUxNCwgXHViYjE4XHViZTQ0LCBcdWI2MTBcdWIyOTQgXHVhZGMwXHVjMmUwIFx1YWQ2Y1x1YmE0ZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJiMThcdWJlNDRcdWIyOTQgXHViOWU0XHVjNmIwIFx1YjE5Mlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmIxOFx1YmU0NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzNjXHViODVjXHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkYzBcdWMyZTAgXHVhZDZjXHViYTRkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0LCBcdWQyYjlcdWM4MTUgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzljMFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHViYjE4XHVjOWMwXHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWFkYzBcdWMyZTAgXHVhZDZjXHViYTRkXHViOWM4XHViMmU0IFx1YjJlNFx1Yjk3NFx1YmE3MCwgXHVjNTkxXHVjMjE4LCBcdWM3NGNcdWMyMTgsIDAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzk0XHViNTE0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNzkwXHVjNzIwXHViODZkXHVhYzhjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJiMThcdWM5YzBcdWI5N2MgXHViZTY4XHViOWFjIFx1YjA5OFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZGMwXHVjMmUwIFx1YWQ2Y1x1YmE0ZFx1YjNjNCBcdWM3NzRcdWM2YTlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJiMThcdWM5YzBcdWI5N2MgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHViMDk4LCBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHVhY2ZjXHVhYzcwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ3JhdmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjcxcHg7IHdpZHRoOjM0MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmIxOFx1YzljMFx1YWMwMCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWUzNCBcdWFjYmRcdWM2YjAoXHViYjM4XHVjODFjXHVjNzU4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjKVx1Yjk3YyBcdWMwYjRcdWQzYjRcdWJjZjRcdWM3OTAuIFx1YmIxOFx1YmU0NFx1YjI5NCAoMiwxKVx1YzY0MCAoMywxKVx1YzVkMCBcdWM3ODhcdWFjZTAsIFx1YWRjMFx1YzJlMCBcdWFkNmNcdWJhNGRcdWM3NDAgMFx1Y2QwOFx1YjljY1x1YzVkMCAoMywwKVx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWMxMWMgKDIsMilcdWM1ZDBcdWMxMWMgXHViMDk4XHVjNjI0XHViMjk0IFx1YWQ2Y1x1YmE0ZCBcdWQ1NThcdWIwOThcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWJiMThcdWM5YzBcdWI5N2MgXHViZTYwXHVjODM4XHViMDk4XHVjNjI0XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0MCA0XHVjZDA4XHVjNzc0XHViYTcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD4oMCwwKSAtJmd0OyBcdWIzZDkoMVx1Y2QwOCkgKDEsMCkgLSZndDsgXHViM2Q5KDFcdWNkMDgpICgyLDApIC0mZ3Q7IFx1YjNkOSgxXHVjZDA4KSAoMywwKSAtJmd0OyBcdWFkYzBcdWMyZTBcdWFkNmNcdWJhNGQoMFx1Y2QwOCkgKDIsMikgLSZndDsgXHViM2Q5KDFcdWNkMDgpICgzLDIpPFwvcD5cclxuXHJcbjxwPlx1YWRjMFx1YzJlMCBcdWFkNmNcdWJhNGRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0MCA1XHVjZDA4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIxOFx1YzljMFx1Yzc1OCBcdWIxMDhcdWJlNDQgV1x1YzY0MCBcdWIxOTJcdWM3NzQgSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgVywgSCAmbGU7IDMwKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIxOFx1YmU0NFx1Yzc1OCBcdWFjMWNcdWMyMTggRyAoRyAmZ2U7IDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIEdcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIxOFx1YmU0NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggWFx1YzY0MCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBYICZsdDsgVywgMCAmbGU7IFkgJmx0OyBIKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRjMFx1YzJlMCBcdWFkNmNcdWJhNGRcdWM3NTggXHVjMjE4IEUgKEUgJmdlOyAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBFXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkYzBcdWMyZTAgXHVhZDZjXHViYTRkXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgWDEsIFkxLCBYMiwgWTIsIFQgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFgxLCBZMSlcdWM3NDAgXHVhZGMwXHVjMmUwIFx1YWQ2Y1x1YmE0ZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NzRcdWFjZTAsIChYMiwgWTIpXHViMjk0IFx1YWRmOCBcdWFkYzBcdWMyZTAgXHVhZDZjXHViYTRkXHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YWMxNFx1Yzc0NCBcdWI1NGMsIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzc0XHViMmU0LiAoMCAmbGU7IFgxLCBYMiAmbHQ7IFcsIDAgJmxlOyBZMSwgWTIgJmx0OyBIKSAoWDEsWTEpXHVhY2ZjIChYMixZMilcdWFjMDAgXHVhYzE5XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFRcdWIyOTQgXHVhZGMwXHVjMmUwIFx1YWQ2Y1x1YmE0ZFx1YzVkMFx1YzExYyBcdWIwOThcdWM2MjRcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC4gKC0xMCwwMDAgJmxlOyBUICZsZTsgMTAsMDAwKSBUXHVhYzAwIFx1YzU5MVx1YzIxOFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGMwXHVjMmUwIFx1YWQ2Y1x1YmE0ZFx1Yzc0NCBcdWI0ZTRcdWM1YjRcdWFjMDQgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjA5OFx1YzYyOFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWFkYzBcdWMyZTAgXHVhZDZjXHViYTRkXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM3YTVcdWMxOGNcdWM1ZDAgXHVjNzg4XHVhYzcwXHViMDk4LCBcdWFkNmNcdWJhNGRcdWM1ZDBcdWMxMWMgXHViMDk4XHVjNjI0XHViMjk0IFx1YzljMFx1YzgxMFx1Yzc3NCBcdWJiMThcdWJlNDRcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHViYjE4XHViZTQ0XHVjNjQwIFx1YWRjMFx1YzJlMCBcdWFkNmNcdWJhNGRcdWM3NzQgKDAsIDApXHVjNzc0XHViMDk4IChXLTEsIEgtMSlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDAgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFjZmNcdWFjNzBcdWI4NWMgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YjNjY1x1YzU0NFx1YWMwNFx1YjJlNFx1YmE3NCAmcXVvdDtOZXZlciZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1Y2Q5Y1x1YWQ2Y1x1Yjk3YyBcdWJlNjBcdWM4MzhcdWIwOThcdWM2MmMgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3NCAmcXVvdDtJbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YzY3OFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViYjE4XHVjOWMwXHViOTdjIFx1YmU2MFx1YzgzOFx1YjA5OFx1YzYyNFx1YjI5NFx1YjM3MCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzg2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhhdW50ZWQgR3JhdmV5YXJkIiwiZGVzY3JpcHRpb24iOiI8cD5Ub25pZ2h0IGlzIEhhbGxvd2VlbiBhbmQgU2NhcmVkIEpvaG4gYW5kIGhpcyBmcmllbmRzIGhhdmUgZGVjaWRlZCB0byBkbyBzb21ldGhpbmcgZnVuIHRvIGNlbGVicmF0ZSB0aGUgb2NjYXNpb246IGNyb3NzaW5nIHRoZSBncmF2ZXlhcmQuIEFsdGhvdWdoIFNjYXJlZCBKb2huIGRvZXMgbm90IGZpbmQgdGhpcyBmdW4gYXQgYWxsLCBoZSBmaW5hbGx5IGFncmVlZCB0byBqb2luIHRoZW0gaW4gdGhlaXIgYWR2ZW50dXJlLiBPbmNlIGF0IHRoZSBlbnRyYW5jZSwgdGhlIGZyaWVuZHMgaGF2ZSBiZWd1biB0byBjcm9zcyB0aGUgZ3JhdmV5YXJkIG9uZSBieSBvbmUsIGFuZCBub3cgaXQgaXMgdGhlIHRpbWUgZm9yIFNjYXJlZCBKb2huLiBIZSBzdGlsbCByZW1lbWJlcnMgdGhlIHRhbGVzIGhpcyBncmFuZG1vdGhlciB0b2xkIGhpbSB3aGVuIGhlIHdhcyBhIGNoaWxkLiBTaGUgdG9sZCBoaW0gdGhhdCwgb24gSGFsbG93ZWVuIG5pZ2h0LCAmcXVvdDtoYXVudGVkIGhvbGVzJnF1b3Q7IGFwcGVhciBpbiB0aGUgZ3JhdmV5YXJkLiBUaGVzZSBhcmUgbm90IHVzdWFsIGhvbGVzLCBidXQgdGhleSB0cmFuc3BvcnQgcGVvcGxlIHdobyBmYWxsIGluc2lkZSB0byBzb21lIHBvaW50IGluIHRoZSBncmF2ZXlhcmQsIHBvc3NpYmx5IGZhciBhd2F5LiBCdXQgdGhlIHNjYXJpZXN0IGZlYXR1cmUgb2YgdGhlc2UgaG9sZXMgaXMgdGhhdCB0aGV5IGFsbG93IG9uZSB0byB0cmF2ZWwgaW4gdGltZSBhcyB3ZWxsIGFzIGluIHNwYWNlOyBpLmUuLCBpZiB5b3UgZmFsbCBpbnNpZGUgYSAmcXVvdDtoYXVudGVkIGhvbGUmcXVvdDssIHlvdSBhcHBlYXIgc29tZXdoZXJlIGluIHRoZSBncmF2ZXlhcmQgYSBjZXJ0YWluIHRpbWUgYmVmb3JlIChvciBhZnRlcikgeW91IGVudGVyZWQgdGhlIGhvbGUsIGluIGEgcGFyYWxsZWwgdW5pdmVyc2Ugb3RoZXJ3aXNlIGlkZW50aWNhbCB0byBvdXJzLjxcL3A+XHJcblxyXG48cD5UaGUgZ3JhdmV5YXJkIGlzIG9yZ2FuaXNlZCBhcyBhIGdyaWQgb2YgVyAmdGltZXM7IEggY2VsbHMsIHdpdGggdGhlIGVudHJhbmNlIGluIHRoZSBjZWxsIGF0IHBvc2l0aW9uICgwLDApIGFuZCB0aGUgZXhpdCBhdCAoVy0xLCBILTEpLiAmbmJzcDtEZXNwaXRlIHRoZSBkYXJrbmVzcywgU2NhcmVkIEpvaG4gY2FuIGFsd2F5cyByZWNvZ25pemUgdGhlIGV4aXQsIGFuZCBoZSB3aWxsIGxlYXZlIGFzIHNvb24gYXMgaGUgcmVhY2hlcyBpdCwgZGV0ZXJtaW5lZCBuZXZlciB0byBzZXQgZm9vdCBhbnl3aGVyZSBpbiB0aGUgZ3JhdmV5YXJkIGFnYWluLiBPbiBoaXMgd2F5IHRvIHRoZSBleGl0LCBoZSBjYW4gd2FsayBmcm9tIG9uZSBjZWxsIHRvIGFuIGFkamFjZW50IG9uZSwgYW5kIGhlIGNhbiBvbmx5IGhlYWQgdG8gdGhlIE5vcnRoLCBFYXN0LCBTb3V0aCBvciBXZXN0LiBJbiBlYWNoIGNlbGwgdGhlcmUgY2FuIGJlIGVpdGhlciBvbmUgZ3JhdmVzdG9uZSwgb25lICZxdW90O2hhdW50ZWQgaG9sZSZxdW90Oywgb3IgZ3Jhc3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SWYgdGhlIGNlbGwgY29udGFpbnMgYSBncmF2ZXN0b25lLCB5b3UgY2Fubm90IHdhbGsgb3ZlciBpdCwgYmVjYXVzZSBncmF2ZXN0b25lcyBhcmUgdG9vIGhpZ2ggdG8gY2xpbWIuPFwvbGk+XHJcblx0PGxpPklmIHRoZSBjZWxsIGNvbnRhaW5zIGEgJnF1b3Q7aGF1bnRlZCBob2xlJnF1b3Q7IGFuZCB5b3Ugd2FsayBvdmVyIGl0LCB5b3Ugd2lsbCBhcHBlYXIgc29tZXdoZXJlIGluIHRoZSBncmF2ZXlhcmQgYXQgYSBwb3NzaWJseSBkaWZmZXJlbnQgbW9tZW50IGluIHRpbWUuIFRoZSB0aW1lIGRpZmZlcmVuY2UgZGVwZW5kcyBvbiB0aGUgcGFydGljdWxhciAmcXVvdDtoYXVudGVkIGhvbGUmcXVvdDsgeW91IGZlbGwgaW50bywgYW5kIGNhbiBiZSBwb3NpdGl2ZSwgbmVnYXRpdmUgb3IgemVyby48XC9saT5cclxuXHQ8bGk+T3RoZXJ3aXNlLCB0aGUgY2VsbCBoYXMgb25seSBncmFzcywgYW5kIHlvdSBjYW4gd2FsayBmcmVlbHkgb3ZlciBpdC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5IZSBpcyB0ZXJyaWZmaWVkLCBzbyBoZSB3YW50cyB0byBjcm9zcyB0aGUgZ3JhdmV5YXJkIGFzIHF1aWNrbHkgYXMgcG9zc2libGUuIEFuZCB0aGF0IGlzIHRoZSByZWFzb24gd2h5IGhlIGhhcyBwaG9uZWQgeW91LCBhIHJlbm93bmVkIHByb2dyYW1tZXIuIEhlIHdhbnRzIHlvdSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBncmF2ZXlhcmQsIGNvbXB1dGVzIHRoZSBtaW5pbXVtIHRpbWUgbmVlZGVkIHRvIGdvIGZyb20gdGhlIGVudHJhbmNlIHRvIHRoZSBleGl0LiBTY2FyZWQgSm9obiBhY2NlcHRzIHVzaW5nICZxdW90O2hhdW50ZWQgaG9sZXMmcXVvdDsgaWYgdGhleSBwZXJtaXQgaGltIHRvIGNyb3NzIHRoZSBncmF2ZXlhcmQgcXVpY2tlciwgYnV0IGhlIGlzIGZyaWdodGVuZWQgdG8gZGVhdGggb2YgdGhlIHBvc3NpYmlsaXR5IG9mIGdldHRpbmcgbG9zdCBhbmQgYmVpbmcgYWJsZSB0byB0cmF2ZWwgYmFjayBpbiB0aW1lIGluZGVmaW5pdGVseSB1c2luZyB0aGUgaG9sZXMsIHNvIHlvdXIgcHJvZ3JhbSBtdXN0IHJlcG9ydCB0aGVzZSBzaXR1YXRpb25zLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2dyYXZlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI3MXB4OyB3aWR0aDozNDJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMzogU2FtcGxlIGdyYXZleWFyZDxcL3A+XHJcblxyXG48cD5GaWd1cmUgMyBpbGx1c3RyYXRlcyBhIHBvc3NpYmxlIGdyYXZleWFyZCAodGhlIHNlY29uZCB0ZXN0IGNhc2UgZnJvbSB0aGUgc2FtcGxlIGlucHV0KS4gSW4gdGhpcyBjYXNlIHRoZXJlIGFyZSB0d28gZ3JhdmVzdG9uZXMgaW4gY2VsbHMgKDIsMSkgYW5kICgzLDEpLCBhbmQgYSAmcXVvdDtoYXVudGVkIGhvbGUmcXVvdDsgZnJvbSBjZWxsICgzLDApIHRvIGNlbGwgKDIsMikgd2l0aCBhIGRpZmZlcmVuY2UgaW4gdGltZSBvZiAwIHNlY29uZHMuIFRoZSBtaW5pbXVtIHRpbWUgdG8gY3Jvc3MgdGhlIGdyYXZleWFyZCBpcyA0IHNlY29uZHMsIGNvcnJlc3BvbmRpbmcgdG8gdGhlIHBhdGg6PFwvcD5cclxuXHJcbjxwPigwLDApICZyYXJyOyBFYXN0IDEgc2VjICgxLDApICZyYXJyOyBFYXN0IDEgc2VjICgyLDApICZyYXJyOyBFYXN0IDEgc2VjICgzLDApICZyYXJyOyBob2xlIDAgc2VjICgyLDIpICZyYXJyOyBFYXN0IDEgc2VjICgzLDIpPFwvcD5cclxuXHJcbjxwPklmIHlvdSBkbyBub3QgdXNlIHRoZSAmcXVvdDtoYXVudGVkIGhvbGUmcXVvdDssIHlvdSBuZWVkIGF0IGxlYXN0IDUgc2Vjb25kcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBXIGFuZCBIICgxICZsZTsgVyxIICZsZTsgMzApLiBUaGVzZSBpbnRlZ2VycyByZXByZXNlbnQgdGhlIHdpZHRoIFcgYW5kIGhlaWdodCBIIG9mIHRoZSBncmF2ZXlhcmQuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBHIChHICZnZTsgMCksIHRoZSBudW1iZXIgb2YgZ3JhdmVzdG9uZXMgaW4gdGhlIGdyYXZleWFyZCwgYW5kIGlzIGZvbGxvd2VkIGJ5IEcgbGluZXMgY29udGFpbmluZyB0aGUgcG9zaXRpb25zIG9mIHRoZSBncmF2ZXN0b25lcy4gRWFjaCBwb3NpdGlvbiBpcyBnaXZlbiBieSB0d28gaW50ZWdlcnMgWCBhbmQgWSAoMCAmbGU7IFggJmx0OyBXIGFuZCAwICZsZTsgWSAmbHQ7IEgpLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgRSAoRSAmZ2U7IDApLCB0aGUgbnVtYmVyIG9mICZxdW90O2hhdW50ZWQgaG9sZXMmcXVvdDssIGFuZCBpcyBmb2xsb3dlZCBieSBFIGxpbmVzLiBFYWNoIG9mIHRoZXNlIGNvbnRhaW5zIGZpdmUgaW50ZWdlcnMgWDEsIFkxLCBYMiwgWTIsIFQuIChYMSxZMSkgaXMgdGhlIHBvc2l0aW9uIG9mIHRoZSAmcXVvdDtoYXVudGVkIGhvbGUmcXVvdDsgKDAgJmxlOyBYMSAmbHQ7IFcgYW5kIDAgJmxlOyBZMSAmbHQ7IEgpLiAoWDIsWTIpIGlzIHRoZSBkZXN0aW5hdGlvbiBvZiB0aGUgJnF1b3Q7aGF1bnRlZCBob2xlJnF1b3Q7ICgwICZsZTsgWDIgJmx0OyBXIGFuZCAwICZsZTsgWTIgJmx0OyBIKS4gTm90ZSB0aGF0IHRoZSBvcmlnaW5hbCBhbmQgdGhlIGRlc3RpbmF0aW9uIG9mIGEgJnF1b3Q7aGF1bnRlZCBob2xlJnF1b3Q7IGNhbiBiZSBpZGVudGljYWwuIFQgKC0xMCAwMDAgJmxlOyBUICZsZTsgMTAgMDAwKSBpcyB0aGUgZGlmZmVyZW5jZSBpbiBzZWNvbmRzIGJldHdlZW4gdGhlIG1vbWVudCBzb21lYm9keSBlbnRlcnMgdGhlICZxdW90O2hhdW50ZWQgaG9sZSZxdW90OyBhbmQgdGhlIG1vbWVudCBoZSBhcHBlYXJzIGluIHRoZSBkZXN0aW5hdGlvbiBwb3NpdGlvbjsgYSBwb3NpdGl2ZSBudW1iZXIgaW5kaWNhdGVzIHRoYXQgaGUgcmVhY2hlcyB0aGUgZGVzdGluYXRpb24gYWZ0ZXIgZW50ZXJpbmcgdGhlIGhvbGUuIFlvdSBjYW4gc2FmZWx5IGFzc3VtZSB0aGF0IHRoZXJlIGFyZSBubyB0d28gJnF1b3Q7aGF1bnRlZCBob2xlcyZxdW90OyB3aXRoIHRoZSBzYW1lIG9yaWdpbiwgYW5kIHRoZSBkZXN0aW5hdGlvbiBjZWxsIG9mIGEgJnF1b3Q7aGF1bnRlZCBob2xlJnF1b3Q7IGRvZXMgbm90IGNvbnRhaW4gYSBncmF2ZXN0b25lLiBGdXJ0aGVybW9yZSwgdGhlcmUgYXJlIG5laXRoZXIgZ3JhdmVzdG9uZXMgbm9yICZxdW90O2hhdW50ZWQgaG9sZXMmcXVvdDsgYXQgcG9zaXRpb24gKDAsMCkgYW5kIChXLTEsSC0xKS48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgZmluaXNoIHdpdGggYSBsaW5lcyBjb250YWluaW5nIDAgMCwgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBpZiBpdCBpcyBwb3NzaWJsZSBmb3IgU2NhcmVkIEpvaG4gdG8gdHJhdmVsIGJhY2sgaW4gdGltZSBpbmRlZmluaXRlbHksIG91dHB1dCBOZXZlci4gT3RoZXJ3aXNlLCBwcmludCB0aGUgbWluaW11bSB0aW1lIGluIHNlY29uZHMgdGhhdCBpdCB0YWtlcyBoaW0gdG8gY3Jvc3MgdGhlIGdyYXZleWFyZCBmcm9tIHRoZSBlbnRyYW5jZSB0byB0aGUgZXhpdCBpZiBpdCBpcyByZWFjaGFibGUsIGFuZCBJbXBvc3NpYmxlIGlmIG5vdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2009 F번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: heiler