시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB118327619023.256%

문제

화물차가 출발지 창고에서 짐을 싣고 배송지 창고까지 짐을 운반하려고 한다. 이 도시의 도로망을 나타낸 지도의 예는 다음과 같다.

#A##0##1#
.#..#..#.
.#..#..#.
.###2#.B.

도로망에서 차들은 동, 서, 남, 북의 방향으로만 이동할 수 있고, 지도의 각 문자는 다음과 같은 의미를 가진다.

  • 'A'는 출발지 창고를 나타내고, 지도에서 유일하다.
  • 'B'는 배송지 창고를 나타내고, 지도에서 유일하다.
  • '.'은 차가 들어갈 수 없는 곳을 나타낸다.
  • '#'은 각 도로 셀을 나타낸다. '#'은 기껏해야 두 개의 다른 도로 셀, 또는 교차로, 창고와 인접하다.
  • 숫자 [0-9]는 신호등에 의해 제어되는 교차로를 나타낸다. 교차로는 적어도 세 개의 도로 셀과 인접하다. 교차로들은 0부터 9까지의 번호로 표시된다. 만일 번호 k를 가진 교차로가 있으면, 반드시 0부터 k까지 번호를 가진 교차로가 존재한다. 교차로의 신호등에 대한 설명은 아래에 나온다.

차량의 이동은 다음과 같은 방식으로 분석된다.

  • 화물차가 인접한 도로 셀, 또는 교차로, 창고로 이동하는 데 걸리는 시간을 단위 시간이라고 가정한다. 차량이 어떤 위치에서 멈춰 서 있는 시간도 단위 시간으로 측정된다.
  • 화물차가 진입하려는 방향으로 파란불이 켜져 있을 때만 교차로로 들어갈 수 있다. 그러나 교차로에 들어간 차량은 언제든지 임의의 방향으로 나갈 수 있다.
  • 교차로의 신호등은 동서 방향과 남북 방향, 두 개의 신호가 주기적으로 켜진다. 교차로의 신호는 초기에 동서 방향 또는 남북 방향이 될 수 있다. 교차로의 신호 주기를 나타내는 값 "a b"는 동서 방향의 신호가 a 시간 켜지고, 남북 방향의 신호가 b 시간 켜짐을 의미한다. 예를 들어, 초기에 남북 방향의 신호가 켜지고 주기 값이 "2 3"이면, 차량이 1-3 시간에 남북 방향의 신호가 켜지고, 4-5 시간은 동서 방향, 6-8 시간은 다시 남북 방향의 신호가 켜진다.
  • 출발지 창고에서 배송지 창고까지 최단 경로를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스의 첫째 줄에는 두 개의 정수 m과 n이 주어진다, 여기서 m은 지도를 나타내는 행렬의 행의 크기이고 n은 열의 크기이다(2 ≤ m, n ≤ 20).

그 다음 m개의 줄에는 각 줄마다 n개의 문자가 주어진다. 각 문자는 지도를 구성하는 문자인 '#', '.', 'A', 'B', [0-9]로 구성된다.

그 다음 줄부터는 각 교차로에 대한 정보가 주어진다. 교차로 번호가 0인 것부터 오름차순으로 한 줄에 하나씩 주어진다. 각 줄에는 교차로 번호 i와 '-' 또는 '|', 그 다음으로 두 개의 정수 ai와 bi (1 ≤ ai, bi ≤ 20) 가 빈칸을 사이에 두고 주어진다, 여기서 '-'는 신호등이 초기에 동서 방향의 신호가 켜짐을 나타내고, '|'는 남북 방향의 신호가 켜짐을 나타낸다. ai와 bi는 각각 동서 방향 신호가 켜 있는 시간과 남북 방향 신호가 켜 있는 시간을 나타낸다.

각 테스트 케이스 사이에는 빈 줄 하나가 들어 있고, 두 개의 0으로 시작되는 테스트 케이스는 입력의 끝을 나타낸다. 테스트 케이스는 20개를 넘지 않는다고 가정해도 된다.
 

출력

각 테스트 케이스에 대해, 한 줄에 한 개의 정수를 출력한다. 이 정수는 출발지 창고에서 배송지 창고까지 차량으로 이동하는 데 걸리는 최소 시간이다. 만일 차량이 배송지 창고까지 도달할 수 없으면 "impossible"을 출력한다.
 

예제 입력 1

3 4
A##B
#..#
####

4 9
#A##0##1#
.#..#..#.
.#..#..#.
.###2#.B.
0 - 1 17
1 | 3 5
2 - 2 4

2 2
A.
.B

0 0 

예제 출력 1

3
17
impossible
W3sicHJvYmxlbV9pZCI6IjE0MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NTRcdWJiM2NcdWNjMjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY1NFx1YmIzY1x1Y2MyOFx1YWMwMCBcdWNkOWNcdWJjMWNcdWM5YzAgXHVjYzNkXHVhY2UwXHVjNWQwXHVjMTFjIFx1YzlkMFx1Yzc0NCBcdWMyZTNcdWFjZTAgXHViYzMwXHVjMWExXHVjOWMwIFx1Y2MzZFx1YWNlMFx1YWU0Y1x1YzljMCBcdWM5ZDBcdWM3NDQgXHVjNmI0XHViYzE4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5ZGRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWM2MDhcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuI0EjIzAjIzEjXHJcbi4jLi4jLi4jLlxyXG4uIy4uIy4uIy5cclxuLiMjIzIjLkIuPFwvcHJlPlxyXG5cclxuPHA+XHViM2M0XHViODVjXHViOWRkXHVjNWQwXHVjMTFjIFx1Y2MyOFx1YjRlNFx1Yzc0MCBcdWIzZDksIFx1YzExYywgXHViMGE4LCBcdWJkODFcdWM3NTggXHViYzI5XHVkNWE1XHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM5YzBcdWIzYzRcdWM3NTggXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc1OFx1YmJmOFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvcD5cclxuPHVsPlxyXG48bGk+JiMzOTtBJiMzOTtcdWIyOTQgXHVjZDljXHViYzFjXHVjOWMwIFx1Y2MzZFx1YWNlMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1YzljMFx1YjNjNFx1YzVkMFx1YzExYyBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuPFwvbGk+XHJcbjxsaT4mIzM5O0ImIzM5O1x1YjI5NCBcdWJjMzBcdWMxYTFcdWM5YzAgXHVjYzNkXHVhY2UwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgXHVjOWMwXHViM2M0XHVjNWQwXHVjMTFjIFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YjJlNC48XC9saT5cclxuPGxpPiYjMzk7LiYjMzk7XHVjNzQwIFx1Y2MyOFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjZjNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL2xpPlxyXG48bGk+JiMzOTsjJiMzOTtcdWM3NDAgXHVhYzAxIFx1YjNjNFx1Yjg1YyBcdWMxNDBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAmIzM5OyMmIzM5O1x1Yzc0MCBcdWFlMzBcdWFlY2ZcdWQ1NzRcdWM1N2MgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWI5NzggXHViM2M0XHViODVjIFx1YzE0MCwgXHViNjEwXHViMjk0IFx1YWQ1MFx1Y2MyOFx1Yjg1YywgXHVjYzNkXHVhY2UwXHVjNjQwIFx1Yzc3OFx1YzgxMVx1ZDU1OFx1YjJlNC48XC9saT5cclxuPGxpPlx1YzIyYlx1Yzc5MCBbMC05XVx1YjI5NCBcdWMyZTBcdWQ2MzhcdWI0ZjFcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YzgxY1x1YzViNFx1YjQxOFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFkNTBcdWNjMjhcdWI4NWNcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1YzEzOCBcdWFjMWNcdWM3NTggXHViM2M0XHViODVjIFx1YzE0MFx1YWNmYyBcdWM3NzhcdWM4MTFcdWQ1NThcdWIyZTQuIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YjRlNFx1Yzc0MCAwXHViZDgwXHVkMTMwIDlcdWFlNGNcdWM5YzBcdWM3NTggXHViYzg4XHVkNjM4XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxY1x1YjJlNC4gXHViOWNjXHVjNzdjIFx1YmM4OFx1ZDYzOCBrXHViOTdjIFx1YWMwMFx1YzljNCBcdWFkNTBcdWNjMjhcdWI4NWNcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWJjMThcdWI0ZGNcdWMyZGMgMFx1YmQ4MFx1ZDEzMCBrXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMDBcdWM5YzQgXHVhZDUwXHVjYzI4XHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVhZDUwXHVjYzI4XHViODVjXHVjNzU4IFx1YzJlMFx1ZDYzOFx1YjRmMVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMTI0XHViYTg1XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWIwOThcdWM2MjhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG48cD5cdWNjMjhcdWI3YzlcdWM3NTggXHVjNzc0XHViM2Q5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YmQ4NFx1YzExZFx1YjQxY1x1YjJlNC48XC9wPlxyXG48dWw+XHJcbjxsaT5cdWQ2NTRcdWJiM2NcdWNjMjhcdWFjMDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YjNjNFx1Yjg1YyBcdWMxNDAsIFx1YjYxMFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWMsIFx1Y2MzZFx1YWNlMFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHViMmU4XHVjNzA0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuIFx1Y2MyOFx1YjdjOVx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YmE0OFx1Y2RiMCBcdWMxMWMgXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNFx1YjNjNCBcdWIyZThcdWM3MDQgXHVjMmRjXHVhYzA0XHVjNzNjXHViODVjIFx1Y2UyMVx1YzgxNVx1YjQxY1x1YjJlNC48XC9saT5cclxuXHJcbjxsaT5cdWQ2NTRcdWJiM2NcdWNjMjhcdWFjMDAgXHVjOWM0XHVjNzg1XHVkNTU4XHViODI0XHViMjk0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWQzMGNcdWI3ODBcdWJkODhcdWM3NzQgXHVjZjFjXHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWI5Y2MgXHVhZDUwXHVjYzI4XHViODVjXHViODVjIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVhZDUwXHVjYzI4XHViODVjXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwNCBcdWNjMjhcdWI3YzlcdWM3NDAgXHVjNWI4XHVjODFjXHViNGUwXHVjOWMwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxsaT5cdWFkNTBcdWNjMjhcdWI4NWNcdWM3NTggXHVjMmUwXHVkNjM4XHViNGYxXHVjNzQwIFx1YjNkOVx1YzExYyBcdWJjMjlcdWQ1YTVcdWFjZmMgXHViMGE4XHViZDgxIFx1YmMyOVx1ZDVhNSwgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWMyZTBcdWQ2MzhcdWFjMDAgXHVjOGZjXHVhZTMwXHVjODAxXHVjNzNjXHViODVjIFx1Y2YxY1x1YzljNFx1YjJlNC4gXHVhZDUwXHVjYzI4XHViODVjXHVjNzU4IFx1YzJlMFx1ZDYzOFx1YjI5NCBcdWNkMDhcdWFlMzBcdWM1ZDAgXHViM2Q5XHVjMTFjIFx1YmMyOVx1ZDVhNSBcdWI2MTBcdWIyOTQgXHViMGE4XHViZDgxIFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZDUwXHVjYzI4XHViODVjXHVjNzU4IFx1YzJlMFx1ZDYzOCBcdWM4ZmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWMxMiAmcXVvdDthIGImcXVvdDtcdWIyOTQgXHViM2Q5XHVjMTFjIFx1YmMyOVx1ZDVhNVx1Yzc1OCBcdWMyZTBcdWQ2MzhcdWFjMDAgYSBcdWMyZGNcdWFjMDQgXHVjZjFjXHVjOWMwXHVhY2UwLCBcdWIwYThcdWJkODEgXHViYzI5XHVkNWE1XHVjNzU4IFx1YzJlMFx1ZDYzOFx1YWMwMCBiIFx1YzJkY1x1YWMwNCBcdWNmMWNcdWM5ZDBcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWNkMDhcdWFlMzBcdWM1ZDAgXHViMGE4XHViZDgxIFx1YmMyOVx1ZDVhNVx1Yzc1OCBcdWMyZTBcdWQ2MzhcdWFjMDAgXHVjZjFjXHVjOWMwXHVhY2UwIFx1YzhmY1x1YWUzMCBcdWFjMTJcdWM3NzQgJnF1b3Q7MiAzJnF1b3Q7XHVjNzc0XHViYTc0LCBcdWNjMjhcdWI3YzlcdWM3NzQgMS0zIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIwYThcdWJkODEgXHViYzI5XHVkNWE1XHVjNzU4IFx1YzJlMFx1ZDYzOFx1YWMwMCBcdWNmMWNcdWM5YzBcdWFjZTAsIDQtNSBcdWMyZGNcdWFjMDRcdWM3NDAgXHViM2Q5XHVjMTFjIFx1YmMyOVx1ZDVhNSwgNi04IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWIyZTRcdWMyZGMgXHViMGE4XHViZDgxIFx1YmMyOVx1ZDVhNVx1Yzc1OCBcdWMyZTBcdWQ2MzhcdWFjMDAgXHVjZjFjXHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cclxuPHA+XHVjZDljXHViYzFjXHVjOWMwIFx1Y2MzZFx1YWNlMFx1YzVkMFx1YzExYyBcdWJjMzBcdWMxYTFcdWM5YzAgXHVjYzNkXHVhY2UwXHVhZTRjXHVjOWMwIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IG1cdWFjZmMgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQsIFx1YzVlY1x1YWUzMFx1YzExYyBtXHVjNzQwIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzRcdWFjZTAgblx1Yzc0MCBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzc0XHViMmU0KDIgJmxlOyBtLCBuICZsZTsgMjApLjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgblx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViYjM4XHVjNzkwXHViMjk0IFx1YzljMFx1YjNjNFx1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNzc4ICYjMzk7IyYjMzk7LCAmIzM5Oy4mIzM5OywgJiMzOTtBJiMzOTssICYjMzk7QiYjMzk7LCBbMC05XVx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1YWMwMSBcdWFkNTBcdWNjMjhcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWQ1MFx1Y2MyOFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgMFx1Yzc3OCBcdWFjODNcdWJkODBcdWQxMzAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWMgXHViYzg4XHVkNjM4IGlcdWM2NDAgJiMzOTstJiMzOTsgXHViNjEwXHViMjk0ICYjMzk7fCYjMzk7LCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNzNjXHViODVjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IGFpXHVjNjQwIGJpICgxICZsZTsgYWksIGJpICZsZTsgMjApIFx1YWMwMCBcdWJlNDhcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQsIFx1YzVlY1x1YWUzMFx1YzExYyAmIzM5Oy0mIzM5O1x1YjI5NCBcdWMyZTBcdWQ2MzhcdWI0ZjFcdWM3NzQgXHVjZDA4XHVhZTMwXHVjNWQwIFx1YjNkOVx1YzExYyBcdWJjMjlcdWQ1YTVcdWM3NTggXHVjMmUwXHVkNjM4XHVhYzAwIFx1Y2YxY1x1YzlkMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsICYjMzk7fCYjMzk7XHViMjk0IFx1YjBhOFx1YmQ4MSBcdWJjMjlcdWQ1YTVcdWM3NTggXHVjMmUwXHVkNjM4XHVhYzAwIFx1Y2YxY1x1YzlkMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIGFpXHVjNjQwIGJpXHViMjk0IFx1YWMwMVx1YWMwMSBcdWIzZDlcdWMxMWMgXHViYzI5XHVkNWE1IFx1YzJlMFx1ZDYzOFx1YWMwMCBcdWNmMWMgXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWIwYThcdWJkODEgXHViYzI5XHVkNWE1IFx1YzJlMFx1ZDYzOFx1YWMwMCBcdWNmMWMgXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjOTA0IFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWI0NTAgXHVhYzFjXHVjNzU4IDBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHViNDE4XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMjBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NzRcdWIzYzQgXHViNDFjXHViMmU0LjxiciBcLz5cclxuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWNkOWNcdWJjMWNcdWM5YzAgXHVjYzNkXHVhY2UwXHVjNWQwXHVjMTFjIFx1YmMzMFx1YzFhMVx1YzljMCBcdWNjM2RcdWFjZTBcdWFlNGNcdWM5YzAgXHVjYzI4XHViN2M5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuIFx1YjljY1x1Yzc3YyBcdWNjMjhcdWI3YzlcdWM3NzQgXHViYzMwXHVjMWExXHVjOWMwIFx1Y2MzZFx1YWNlMFx1YWU0Y1x1YzljMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3NCAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48YnIgXC8+XHJcbiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE0MDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYXJnbyBDYXJyaWFnZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBzZWVtaW5nbHkgc3RyYWlnaHRmb3J3YXJkIHRhc2sgc3VjaCBhcyBkcml2aW5nIGNhcmdvIGZyb20gcG9pbnQgQSB0byBwb2ludCBCIGNhbiBzb21ldGltZXMgYmUgdmVyeSB0cmlja3khIEdQUyBzeXN0ZW1zIGNhbiBiZSB2ZXJ5IGhlbHBmdWwgZm9yIFx1ZmIwMW5kaW5nIHJvdXRlcywgYnV0IHVzdWFsbHkgZG9uJnJzcXVvO3QgdGFrZSBhbGwgdGhpbmdzIGludG8gY29uc2lkZXJhdGlvbi4gRm9yIGluc3RhbmNlLCB3aGVuIFx1ZmIwMW5kaW5nIHRoZSBxdWlja2VzdCByb3V0ZSwgZG8gdGhleSBjb25zaWRlciB3YWl0aW5nIGF0IHRyYVx1ZmIwM2MgbGlnaHRzPyBXaGF0IGFib3V0IGNvbmdlc3Rpb24/IE1heWJlIHlvdSBjYW4gd3JpdGUgc3VwZXJpb3Igc29mdHdhcmU/PFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgYmUgZ2l2ZW4gYSBzdHJlZXQgbWFwIGNvbnRhaW5pbmcgcm9hZHMsIG51bWJlcmVkIGludGVyc2VjdGlvbnMgKHdpdGggdHJhXHVmYjAzYyBsaWdodHMpLCBhbmQgdHdvIHdhcmVob3VzZXMuIFlvdXIgdGFzayBpcyB0byBcdWZiMDFuZCB0aGUgZmFzdGVzdCByb3V0ZSB0byBkcml2ZSBhIHRydWNrIGZyb20gd2FyZWhvdXNlIEEgdG8gd2FyZWhvdXNlIEIuPFwvcD5cclxuXHJcbjxwPlN0cmVldCBtYXBzIGFyZSBhbHdheXMgZHJhd24gb24gYSBncmlkLCBhbmQgbG9vayBsaWtlIHRoaXM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiNBIyMwIyMxI1xyXG4uIy4uIy4uIy5cclxuLiMuLiMuLiMuXHJcbi4jIyMyIy5CLjxcL3ByZT5cclxuXHJcbjxwPkZpZ3VyZSAyOiBBIHN0cmVldCBtYXAgd2l0aCB3YXJlaG91c2VzLCByb2FkcywgYW5kIGludGVyc2VjdGlvbnMuPFwvcD5cclxuXHJcbjxwPjxiciBcLz5cclxuQWRqYWNlbmN5IG9uIHRoaXMgbWFwIGlzIGRlXHVmYjAxbmVkIGFzIG5laWdoYm9yaW5nIG5vcnRoLCBzb3V0aCwgZWFzdCwgb3Igd2VzdC4gVGhlIG9ubHkgc3ltYm9scyB0aGF0IGFwcGVhciBvbiB0aGUgbWFwIGFyZSB0aGUgZm9sbG93aW5nOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgIyBjaGFyYWN0ZXIgaW5kaWNhdGVzIGEgcm9hZCBjZWxsIHRoYXQgdHJ1Y2tzIGNhbiBkcml2ZSBvbi4gUm9hZHMgYXJlIGFkamFjZW50IHRvIGF0IG1vc3QgdHdvIG90aGVyIHJvYWQsIGludGVyc2VjdGlvbiwgb3Igd2FyZWhvdXNlIGNlbGxzLjxcL2xpPlxyXG5cdDxsaT5BIHNpbmdsZSBudW1iZXIgWzAtOV0gbWFya3MgYW4gaW50ZXJzZWN0aW9uIGNvbnRyb2xsZWQgYnkgYSB0cmFcdWZiMDNjIGxpZ2h0LiBJbnRlcnNlY3Rpb25zIGFyZSBhZGphY2VudCB0byBhdCBsZWFzdCB0aHJlZSByb2FkIGNlbGxzLiBJbnRlcnNlY3Rpb25zIGFyZSB1bmlxdWVseSBudW1iZXJlZCBzZXF1ZW50aWFsbHk6IG5vIG51bWJlciB3aWxsIGFwcGVhciB1bmxlc3MgYWxsIG5vbm5lZ2F0aXZlIGludGVnZXJzIGxlc3MgdGhhbiBpdCBhbHNvIGFwcGVhciBvbiB0aGUgbWFwLiBUaGUgYmVoYXZpb3Igb2YgdHJhXHVmYjAzYyBsaWdodHMgd2lsbCBiZSBkZXNjcmliZWQgYmVsb3cuPFwvbGk+XHJcblx0PGxpPkV4YWN0bHkgb25lIGNoYXJhY3RlciBBIG1hcmtzIHRoZSBsb2NhdGlvbiBvZiB0aGUgd2FyZWhvdXNlIHdoZXJlIHlvdXIgdHJ1Y2tzIHN0YXJ0LjxcL2xpPlxyXG5cdDxsaT5FeGFjdGx5IG9uZSBjaGFyYWN0ZXIgQiBtYXJrcyB0aGUgbG9jYXRpb24gb2YgdGhlIHdhcmVob3VzZSB3aGVyZSB5b3UmcnNxdW87ZCBsaWtlIHRvIHNoaXAgeW91ciBjYXJnbyB0by48XC9saT5cclxuXHQ8bGk+QSAuIGNoYXJhY3RlciBpcyBqdXN0IGdyYXNzLiBZb3UgY2Fubm90IGRyaXZlIG9uIHRoZXNlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBoYXZlIG9uZSBjYXJnbyB0cnVjayB0aGF0IHN0YXJ0cyBhdCB3YXJlaG91c2UgQSwgYW5kIHlvdSBhcmUgdHJ5aW5nIHRvIGRyaXZlIGl0IHRvIHdhcmVob3VzZSBCIGFjY29yZGluZyB0byB0aGUgcnVsZXMgYmVsb3cuIEZvciBzaW1wbGljaXR5LCB3ZSBjYW4gYWxzbyBkaXNjcmV0aXplIHRpbWUgaW50byBhdG9taWMgdW5pdHMsIG9yIHR1cm5zLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uIGEgc2luZ2xlIHR1cm4sIHlvdSBtYXkgbW92ZSB0aGUgdHJ1Y2sgb250byBhbiBhZGphY2VudCByb2FkLCBpbnRlcnNlY3Rpb24sIG9yIHdhcmVob3VzZSBjZWxsLCBvciBzaW1wbHkgcmVtYWluIGluIHRoZSBzYW1lIGNlbGwuPFwvbGk+XHJcblx0PGxpPkEgdHJ1Y2sgbWF5IG9ubHkgbW92ZSBpbnRvIGFuIGludGVyc2VjdGlvbiBjZWxsIGlmIHRoZSB0cmFcdWZiMDNjIGxpZ2h0IGZvciB0aGUgaW50ZXJzZWN0aW9uIGlzIGdyZWVuIGluIHRoZSBkaXJlY3Rpb24gdGhlIHRydWNrIGlzIGVudGVyaW5nIGZyb20gZHVyaW5nIHRoYXQgdHVybi4gSG93ZXZlciwgYSB0cnVjayBvbiBhbiBpbnRlcnNlY3Rpb24gY2VsbCBjYW4gZXhpdCBpbiBhbnkgZGlyZWN0aW9uIGF0IGFueSB0aW1lLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkludGVyc2VjdGlvbnMgd2l0aCB0cmFcdWZiMDNjIGxpZ2h0cyBwZXJpb2RpY2FsbHkgYWxsb3cgZWl0aGVyIGVhc3Qtd2VzdCBvciBub3J0aC1zb3V0aCB0cmFcdWZiMDNjIFx1ZmIwMm93LCBidXQgbm90IGJvdGggYXQgdGhlIHNhbWUgdGltZS4gVGhleSBhcmUgZGVzY3JpYmVkIGJ5IGFuIGluaXRpYWwgZGlyZWN0aW9uIGFuZCB0d28gbnVtYmVycyBpbmRpY2F0aW5nIHRoZSBlYXN0LXdlc3QgYW5kIG5vcnRoLXNvdXRoIHBlcmlvZHMsIHJlc3BlY3RpdmVseS4gRm9yIGV4YW1wbGUsIGFuIGludGVyc2VjdGlvbiBpbml0aWFsbHkgZ3JlZW4gb24gdGhlIG5vcnRoLXNvdXRoIGRpcmVjdGlvbiBkZXNjcmliZWQgYnkgJmxkcXVvOzIgMyZyZHF1bzsgd2lsbCBoYXZlIGEgZ3JlZW4gbGlnaHQgZmFjaW5nIG5vcnRoIGFuZCBzb3V0aCBvbiB0dXJucyAxLTMgaW5jbHVzaXZlLCBmYWNpbmcgZWFzdCBhbmQgd2VzdCBvbiB0dXJucyA0LTUsIGFuZCBhZ2FpbiBub3J0aCBhbmQgc291dGggb24gdHVybnMgNi04LCBldGMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgdGVzdCBcdWZiMDFsZSB3aWxsIGNvbnRhaW4gbXVsdGlwbGUgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGJlZ2lucyB3aXRoIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMsIG0gYW5kIG4sIHNlcGFyYXRlZCBieSBzcGFjZXMuIFRoZSBzdHJlZXQgbWFwIGNvbnNpc3RzIG9mIG0gcm93cyAoZWFzdC13ZXN0KSBhbmQgbiBjb2x1bW5zIChub3J0aC1zb3V0aCkgb2YgZ3JpZCBjZWxscyAoMiAmbGU7IG0sbiAmbGU7IDIwKS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbSBsaW5lcyBjb250YWluIG4gY2hhcmFjdGVycyBlYWNoLCB3aGljaCBkZXNjcmliZSB0aGUgbWFwIHVzaW5nIHRoZSBzeW1ib2xzIGRlXHVmYjAxbmVkIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudCBhYm92ZS4gRm9yIGVhY2ggbnVtYmVyZWQgaW50ZXJzZWN0aW9uIHRoYXQgYXBwZWFycyBpbiB0aGUgbWFwLCBpbiBhc2NlbmRpbmcgb3JkZXIgYmVnaW5uaW5nIHdpdGggMCwgdGhlcmUgd2lsbCBiZSBhIGxpbmUgb2YgdGV4dCB3aXRoIHRoZSBpbnRlcnNlY3Rpb24gbnVtYmVyIGZvbGxvd2VkIGJ5IGVpdGhlciBhICZsc3F1bzstJnJzcXVvOyBvciAmbHNxdW87fCZyc3F1bzsgY2hhcmFjdGVyIGFuZCB0d28gaW50ZWdlcnMsIGE8c3ViPmk8XC9zdWI+IGFuZCBiPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICxiPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCksIHRoZSBkdXJhdGlvbiAoaW4gdHVybnMpIG9mIHRoZSBlYXN0LXdlc3QgYW5kIG5vcnRoc291dGggcGVyaW9kcyBvZiB0aGUgbGlnaHQsIHJlc3BlY3RpdmVseS4gQSAmbHNxdW87LSZyc3F1bzsgaW5kaWNhdGVzIHRoYXQgdGhlIHRyYVx1ZmIwM2MgbGlnaHQgaXMgaW5pdGlhbGx5IGdyZWVuIGluIHRoZSBlYXN0LXdlc3QgZGlyZWN0aW9uLCB3aGlsZSBhICZsc3F1bzt8JnJzcXVvOyBpbmRpY2F0ZXMgdGhhdCBpdCBpcyBpbml0aWFsbHkgZ3JlZW4gaW4gdGhlIG5vcnRoLXNvdXRoIGRpcmVjdGlvbi48XC9wPlxyXG5cclxuPHA+QSBibGFuayBsaW5lIHNlcGFyYXRlcyBpbnB1dCB0ZXN0IGNhc2VzLCBhcyBzZWVuIGluIHRoZSBzYW1wbGUgaW5wdXQgYmVsb3cuIEEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgbnVtYmVycyAmbGRxdW87MCAwJnJkcXVvOyBtYXJrcyB0aGUgZW5kIG9mIGlucHV0OyBkbyBub3QgcHJvY2VzcyB0aGlzIGNhc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB5b3VyIHByb2dyYW0gc2hvdWxkIHByaW50IG9uZSBpbnRlZ2VyIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBtaW5pbXVtIG51bWJlciBvZiB0dXJucyBpdCB0YWtlcyB0byBkcml2ZSB5b3VyIHRydWNrIGZyb20gd2FyZWhvdXNlIEEgdG8gd2FyZWhvdXNlIEIuIElmIGl0IGlzIG5vdCBwb3NzaWJsZSB0byBnZXQgdG8gd2FyZWhvdXNlIEIsIHByaW50IGEgc2luZ2xlIHdvcmQgJmxkcXVvO2ltcG9zc2libGUmcmRxdW87LiBPdXRwdXQgY29ycmVzcG9uZGluZyB0byB0aGUgc2FtcGxlIGlucHV0IHdvdWxkIGFwcGVhciBhcyBzdWNoOjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

University > Stanford Local ACM Programming Contest > SLPC 2008 C번

  • 문제를 번역한 사람: author5