Grid Navigation with Sequential Teleports

You are given an $n \times m$ grid. Each cell is either a walkable path denoted by . or an obstacle denoted by #. You start at cell \( (s_x,s_y) \) and can move one step at a time to any of the four neighbors: up, down, left, or right, provided that you remain within the grid boundaries \( (1\le x\le n,\;1\le y\le m) \) and do not step into an obstacle.

In addition, there are \( p \) portals located at cells \( (a_1,b_1), (a_2,b_2), \dots, (a_p,b_p) \) (all guaranteed to be walkable). Also provided are \( q \) teleport endpoints with coordinates \( (c_1,d_1), (c_2,d_2), \dots, (c_q,d_q) \) (also walkable). When you arrive at any portal, if you have used exactly \( i \) teleports so far (starting with \( i=0 \)), you may choose to teleport instantly (at zero extra cost) to \( (c_{i+1},d_{i+1}) \) provided \( i < q \). After the \( q\text{-th} \) teleport the portals become inactive. Note that the teleport destination depends solely on the number of teleports used and not on which portal you step into.

The problem comes in two flavours. In one, you are to find the minimum number of moving steps required to reach every cell in the grid; in the other, you are only interested in reaching a specified target cell \( (t_x,t_y) \). (It is guaranteed that the coordinates provided for the portals, endpoints, the start, and, if applicable, the target, are all walkable and distinct.)

Note: All formulas must be rendered in \( \LaTeX \) format. For instance, the grid boundaries are given by \(1 \le x \le n\) and \(1 \le y \le m\).

inputFormat

The input is given as follows:

// First line: two integers n and m
n m

// Next n lines: each is a string of length m, representing the grid
line1
line2
...
line_n

// Next line: two integers s_x and s_y (starting position)

s_x s_y

// Next line: integer p, the number of portals

p

// Next p lines: each contains two integers representing a portal's coordinates
 a_1 b_1
 a_2 b_2
 ...
 a_p b_p

// Next line: integer q, the number of teleport endpoints

q

// Next q lines: each contains two integers representing the teleport endpoint, in order
 c_1 d_1
 c_2 d_2
 ...
 c_q d_q

// Next line: an integer mode
// If mode is 0, you are to output the minimum number of steps to reach every cell.
// If mode is 1, an additional line follows with two integers t_x and t_y representing the target.

mode
[ t_x t_y ] // This line appears only if mode == 1

outputFormat

If mode is 0, output n lines, each containing m space-separated integers. For each cell that is unreachable, output -1.

If mode is 1, output a single integer representing the minimum number of steps required to reach the target cell \( (t_x,t_y) \); if the target is unreachable, output -1.

sample

3 4
.#..
....
..#.
1 1
2
1 3
3 1
2
2 4
3 4
0

0 -1 4 3
1 2 3 2
2 3 -1 3