화물차

화물차 한 대가 출발지 창고에서 짐을 싣고 배송지 창고까지 운반하려고 한다. 도시는 격자 지도로 주어지며, 도로망은 다음과 같은 형태일 수 있다.

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

차량은 동, 서, 남, 북 네 방향으로만 이동할 수 있다. 지도의 각 문자는 다음을 뜻한다.

• A는 출발지 창고이며, 지도에 정확히 하나만 있다.
• B는 배송지 창고이며, 지도에 정확히 하나만 있다.
• .은 차량이 들어갈 수 없는 칸이다.
• #은 도로 칸이다. 하나의 도로 칸은 다른 도로 칸, 교차로, 창고를 합쳐 최대 두 칸과 인접한다.
• 숫자 0부터 9까지는 신호등이 있는 교차로를 나타낸다. 교차로는 적어도 세 개의 도로 칸과 인접한다. 교차로 번호는 0부터 시작해 빠짐없이 붙는다. 즉 번호 k의 교차로가 있다면 0, 1, ..., k번 교차로가 모두 존재한다.

차량의 이동 시간은 다음 규칙으로 계산한다.

• 인접한 도로 칸, 교차로, 창고로 이동하는 데에는 1시간 단위가 걸린다. 한 위치에서 기다리는 시간도 1시간 단위로 센다.
• 차량은 진입하려는 방향의 신호가 파란불일 때에만 교차로로 들어갈 수 있다. 단, 이미 교차로에 들어간 차량은 어느 방향으로든 바로 나갈 수 있다.
• 각 교차로의 신호등은 동서 방향 신호와 남북 방향 신호를 번갈아 켠다. 처음 켜져 있는 방향은 교차로마다 다를 수 있다. 주기 값 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 중 하나이다.

그다음에는 각 교차로의 정보가 번호가 작은 순서대로 한 줄에 하나씩 주어진다. 각 줄은 교차로 번호 i, 문자 - 또는 |, 그리고 두 정수 ai, bi로 이루어진다. (1 <= ai, bi <= 20) -는 처음에 동서 방향 신호가 켜져 있음을, |는 처음에 남북 방향 신호가 켜져 있음을 뜻한다. ai와 bi는 각각 동서 방향 신호와 남북 방향 신호가 켜져 있는 시간이다.

테스트 케이스 사이에는 빈 줄 하나가 있을 수 있다. 0 0이 주어지면 입력이 끝난다. 테스트 케이스의 수는 20개를 넘지 않는다.

각 테스트 케이스마다 한 줄에 하나씩 답을 출력한다. 답은 출발지 창고에서 배송지 창고까지 이동하는 데 걸리는 최소 시간이다. 배송지 창고에 도달할 수 없으면 impossible을 출력한다.