Cargo Truck

A cargo truck must carry goods from a starting warehouse to a destination warehouse. The city is given as a grid map, and the road network may have the following shape.

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

The truck may move only east, west, south, or north. Each character in the map has the following meaning.

• A is the starting warehouse, and appears exactly once.
• B is the destination warehouse, and appears exactly once.
• . is a cell the truck cannot enter.
• # is a road cell. A road cell is adjacent to at most two cells total among other road cells, intersections, and warehouses.
• A digit from 0 to 9 is an intersection controlled by a traffic light. An intersection is adjacent to at least three road cells. Intersection numbers start at 0 and have no gaps: if intersection k exists, then all intersections 0, 1, ..., k also exist.

Travel time is measured by these rules.

• Moving to an adjacent road cell, intersection, or warehouse takes 1 unit of time. Waiting in place is also measured in units of 1.
• The truck may enter an intersection only when the light is green for the direction from which it is entering. Once the truck is inside an intersection, it may leave in any direction immediately.
• Each intersection alternates between an east-west signal and a north-south signal. The initial direction may differ by intersection. A period value a b means the east-west signal is green for a time units and the north-south signal is green for b time units. If the north-south signal is initially green and the period is 2 3, then the north-south signal is green during times 1--3, the east-west signal during times 4--5, and the north-south signal again during times 6--8.

Find the minimum time needed to travel from the starting warehouse to the destination warehouse.

The input consists of multiple test cases. The first line of each test case contains two integers m and n, where m is the number of rows in the map and n is the number of columns. (2 <= m, n <= 20)

The next m lines each contain one string of length n. Every character is one of #, ., A, B, or a digit from 0 to 9.

Then the information for each intersection is given, one line per intersection in increasing order of intersection number. Each line contains the intersection number i, either - or |, and two integers ai and bi. (1 <= ai, bi <= 20) - means the east-west signal is initially green, and | means the north-south signal is initially green. ai and bi are the green durations for the east-west and north-south signals, respectively.

There may be one blank line between test cases. The line 0 0 ends the input. There are at most 20 test cases.

For each test case, output one line containing the minimum time required to move from the starting warehouse to the destination warehouse. If the destination warehouse cannot be reached, output impossible.