A seemingly straightforward task such as driving cargo from point A t o point B can sometimes be very tricky! GPS systems can be very helpful for finding routes, but usually don’t take all things in to consideration. For instance, when finding the quickest route, do they consider waiting at traffic lights? What about congestion? Maybe you can write superior software? In this problem, you will be given a street map containing roads, numbered int ersections (with traffic lights), and two warehouses. Your task is to find the fastest route to drive a truck from warehouse A to warehouse B. Street maps are always drawn on a grid, and look like this:

#A##0##1#
.#..#..#.
.#..#..#.
.###2#.B.
Figure 2: A street map with warehouses, roads, and intersections.

• A # character indicates a road cell that trucks can drive on. Roads are adjacent to at most two other road, intersection, or warehouse cells.
• A single number [0-9] marks an intersection controlled by a traffic light. Intersections are a djacent to at least three road cells. Intersections are uniquely numbered sequentially: no number will appear unless all nonnegative integers less than it also appear on the map. The behavior of traffic lights will be described below.
• Exactly one character A marks the location of the warehouse where your trucks start. .
• Exactly one character B marks the location of the warehouse where you’d like to ship your cargo to.
• A . character is just grass. You cannot drive on these.

• On a single turn, you may move the truck onto an adjacent road, intersection, or warehouse cell, or simply remain in the same cell.
• A truck may only move into an intersection cell if the traffic light for the intersection is green in the direction the truck is entering from during that turn. However, a truck on an intersection cell can exit in any direction at any time.

입력

• Each test case begins with a single line containing two integers, m and n , separated by spaces. The street map consists of m rows (east-west) and n columns (north-south) of grid cells (2 ≤ m, n ≤ 20).
• The next m lines contain n characters each, which describe the map using the symbols defined in the problem statement above. For each numbered intersection that appears in the map, in ascending order beginning with 0, there will be a line of text with the intersection number fol lowed by either a ‘ - ’ or ‘ | ’ character and two integers, ai and bi (1 ≤ ai , bi ≤ 100), the duration (in turns) of the east-west and north-south periods of the light, respectively. A ‘ - ’ indicates that the traffic light is initially green in the east-west direction, while a ‘ | ’ indicates that it is initially green in the north-south direction.

출력

입출력 예

입력

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

출력

3

입력

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

출력

17

입력

2 2
A.
.B

출력

impossible

출처:standford/2008/