Problem Statement

Takahashi is trapped in an N \times M grid-shaped labyrinth. Each cell of the grid is either a passage (.) or a wall (#). A cell is denoted by (r, c) (row r, column c), where both rows and columns are numbered starting from 1. Row numbers increase from top to bottom, and column numbers increase from left to right. That is, from cell (r, c), "up" refers to cell (r-1, c), "down" refers to cell (r+1, c), "left" refers to cell (r, c-1), and "right" refers to cell (r, c+1).

Takahashi is currently at cell (S_r, S_c) and is trying to escape by reaching the exit at cell (G_r, G_c).

There are K guard robots patrolling the labyrinth, and the i-th guard robot's initial position is cell (P_i, Q_i). Different guard robots may be initially placed on the same cell.

Each guard robot's movement is deterministically determined based solely on Takahashi's position, according to the movement rules described below. Takahashi knows the entire structure of the labyrinth and all the movement rules of the guard robots.

Takahashi and the guard robots repeat turns as follows. The first turn is turn 1, followed by turns 2, 3, \ldots. No capture check is performed at the start of the game (before step 1 of turn 1). Each turn proceeds in the following order:

1. Takahashi's movement: Takahashi chooses to either move 1 cell to an adjacent passage cell in one of the four directions (up, down, left, right), or stay on his current cell. He cannot move to a wall cell or outside the grid. Staying on the current cell is always an available choice.
2. Capture check 1: After Takahashi's movement, if Takahashi is on the same cell as any guard robot, Takahashi is caught and escape fails. In this case, the remaining steps of this turn are not executed.
3. Escape check: If Takahashi was not caught in capture check 1, and Takahashi is at the exit (G_r, G_c), then escape succeeds. In this case, the remaining steps of this turn are not executed.
4. Guard robots' movement: If neither escape success nor escape failure has occurred, all guard robots simultaneously move 1 step (movement rules described below). Each robot determines its destination independently of the other robots. Multiple robots are allowed to occupy the same cell.
5. Capture check 2: After the guard robots' movement, if Takahashi is on the same cell as any guard robot, Takahashi is caught and escape fails.

These turns repeat until either escape success or escape failure occurs.

Guard Robot Movement Rules

Each guard robot either moves 1 cell to an adjacent passage cell in one of the four directions (up, down, left, right), or stays on its current cell. It cannot move to a wall cell or outside the grid.

Each guard robot's destination is determined as follows. First, enumerate the movement candidates. The candidates are: moving up, down, left, or right where the destination is within the grid and is a passage, as well as staying on the current cell (at most 5 candidates).

For each candidate, compute the Manhattan distance from the robot's position after the move to Takahashi's position after his movement in that turn (his position after step 1). Here, the Manhattan distance between cells (r_1, c_1) and (r_2, c_2) is |r_1 - r_2| + |c_1 - c_2|, regardless of whether there are walls in between.

Among the candidates, the one that minimizes this Manhattan distance is selected. If there are multiple candidates with the minimum Manhattan distance, the one with the highest priority is selected according to the priority order: up, down, left, right, stay (listed from highest to lowest priority).

What to Output

Determine whether Takahashi can successfully escape when he acts optimally. Here, "acting optimally" means that if there exists a sequence of actions that leads to escape success, he chooses such a sequence, and among those, he acts to minimize the turn number at which escape succeeds.

If escape is possible, output the minimum turn number at which escape succeeds.

If Takahashi cannot escape no matter how he acts (e.g., he is inevitably caught before reaching the exit, or he can avoid being caught but can never reach the exit), output -1.

Constraints

• 1 \leq N \leq 8
• 1 \leq M \leq 8
• 0 \leq K \leq 2
• 1 \leq S_r \leq N
• 1 \leq S_c \leq M
• 1 \leq G_r \leq N
• 1 \leq G_c \leq M
• 1 \leq P_i \leq N (1 \leq i \leq K)
• 1 \leq Q_i \leq M (1 \leq i \leq K)
• (S_r, S_c) \neq (G_r, G_c)
• Takahashi's initial position, the exit, and each guard robot's initial position are all passages (.).
• Takahashi's initial position is different from the initial position of every guard robot.
• All input values are integers (except for the grid strings).

Sample Input 1

3 3 0
1 1
1 3
...
...
...

Sample Output 1

2

Sample Input 2

3 1 1
1 1
3 1
2 1
.
.
.

Sample Output 2

-1

Sample Input 3

5 5 1
1 1
5 5
3 3
.....
.###.
.#...
.#.#.
.....

Sample Output 3

16

Sample Input 4

8 8 2
1 1
8 8
1 8
8 1
........
.######.
.#....#.
.#.##.#.
.#.##.#.
.#....#.
.######.
........

Sample Output 4

-1

Sample Input 5

1 2 0
1 1
1 2
..

Sample Output 5

1