Background

Teleking plays with portals every day.

Problem Description

You are given a 2D grid of size $n \times m$.

In the grid, . is a passable cell, and # is an impassable obstacle.

Each time, you may move to a cell that is 4-connected to your current position and stays within the boundary.

More precisely, if you are currently at $(x,y)$, you may move to one of $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, $(x,y+1)$, and it is guaranteed that at any time your coordinates $(x,y)$ satisfy $1 \le x \le n, 1 \le y \le m$.

Starting from $(sx,sy)$, you want to know the minimum number of steps needed to reach any position.

But that is too easy, so Teleking, who is skilled with portals, built $p$ portals on this grid, with coordinates $(a_1,b_1),(a_2,b_2),...,(a_p,b_p)$.

Teleking also designed $q$ destinations, with coordinates $(c_1,d_1),(c_2,d_2),...,(c_q,d_q)$.

Suppose you have used portals $i$ times. When you arrive at any portal, you may choose to teleport directly to $(c_{i+1},d_{i+1})$. After the $q$-th teleport, all portals will become invalid.

Therefore, the teleport destination depends only on how many times you have teleported, and has nothing to do with which portal you entered. We may treat all portals as equivalent.

It is guaranteed that the positions of the $p$ portals and the $q$ destinations are not obstacles.

It is guaranteed that every position given by the input coordinates is a passable cell, and all these coordinates are pairwise distinct.

However, sometimes Teleking does not want to know the minimum steps to every cell. He may only want the minimum number of movement steps to one target $(tx,ty)$. You will learn this preference from the input format (it is guaranteed that $(tx,ty)$ is not an obstacle).

Input Format

The first line contains a positive integer $opt$.

The second line contains two positive integers $n,m$, representing the size of the grid.

Then follow $n$ lines, each containing $m$ characters, describing the grid.

The next line contains several positive integers. The first four numbers are $sx,sy,p,q$. If $opt=1$, two extra numbers $tx,ty$ are given, meaning Teleking only wants to know the minimum number of movement steps from the start to $(tx,ty)$.

Then follow $p$ lines, each containing two positive integers, representing $a_i,b_i$.

Finally follow $q$ lines, each containing two positive integers, representing $c_i,d_i$.

Output Format

If $opt=0$, output an $n \times m$ matrix. The number in row $i$ column $j$ is the minimum number of movement steps from $(sx,sy)$ to $(i,j)$. If it is impossible to reach or the cell is an obstacle, output -1.

Otherwise, output one number: the minimum number of movement steps from $(sx,sy)$ to $(tx,ty)$. If it is impossible to reach, output -1.

Note: Teleporting to change position is not counted as a movement step.

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

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

Hint

Sample explanation:

Take traveling from the start $(3,4)$ to $(1,1)$ as an example: first $(3,4)\to(2,4)$, then use a portal and teleport for the first time to $(1,4)$. Then $(1,4)\to(2,4)$, use a portal for the second time and arrive at $(2,1)$, and finally $(2,1)\to(1,1)$. We used portals twice and walked $3$ steps, so the movement count of this path is $3$. It can be proven that there is no better solution.

This problem uses bundled subtasks.

$A$: It is guaranteed that $opt=1$.

$B$: It is guaranteed that there are no impassable obstacles # in the grid.

Constraints: For all testdata, $1 \le n,m \le 1000$, $0 \le p,q \le n \times m$, $0 \le opt \le 1$。

Translated by ChatGPT 5