시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB34151340.625%

문제

The full-board residents of the famous but misnamed Adephagia School For Boys feel hard done by. Recent savings have seen dinnertime puddings cut back to a single biscuit while the masters finish their meals with fine raspberry jelly every night. Although the choice of custard cream or bourbon is not a bad one, the children hunger for the raspberry-filled delight and have planned a midnight raid.

A child must make it from their dorm, across the school to the kitchen without being seen by the patrolling masters. In any turn a child can stand still, or move to a horizontally or vertically neighbouring cell. Each turn the patrolling masters will move a step along their route. When they reach the end of their route, they will turn and continue to retrace their steps indefinitely. A child will be caught if the child and a master are on the same row or column with no blocked area between them.

If the child can make it to the fridge in the kitchen unseen, we recognise they can either make it back to their bed unseen or get caught fully of jelly and not care. See the first example, where the child can reach the fridge after 26 turns, even though it gets spotted at that same time.

입력

  • One line consisting of two positive integers r c (1 < r, c ≤ 60), the size of the school in rows and columns.
  • One line consisting of two pairs of bracketed positive integers, the row and column coordinates of the starting bed in the dormitory and the fridge in the kitchen respectively.
  • Another r lines, each containing a string of c characters with the following meaning:
    • ’.’: Walkable area
    • ’#’: Blocked area
  • One line consisting of a single integer p (1 ≤ p ≤ 200) representing the number of patrolling masters.
  • Another p lines, each a size-prefixed list of between 1 and 7 space-separated bracketed (r, c) coordinates representing a contiguous path for the master to patrol.

All ‘special’ coordinates (locations of the bed, fridge, and masters) will be marked as walkable on the map.

출력

On a single line print the minimum number of turns for the child to reach the jelly. If the child cannot reach the jelly, output IMPOSSIBLE.

예제 입력 1

5 5
(2 5) (5 3)
.....
.#.#.
.#.#.
....#
.#.##
1
6 (4 2) (4 3) (3 3) (2 3) (1 3) (1 2)

예제 출력 1

26

예제 입력 2

5 4
(1 4) (5 4)
....
..#.
###.
....
###.
2
2 (2 2) (2 1)
4 (4 1) (4 2) (4 3) (4 3)

예제 출력 2

IMPOSSIBLE