Description

The legion is an $n$ by $m$ matrix, and each cell represents a member of the Scarlet Vanguard. An infected person spreads the plague to the four adjacent cells (up, down, left, right) every hour, until everyone is infected. You already know the positions of the infection sources. Your task is to compute the time when each of the Scarlet Vanguard’s lords becomes infected, and report it to the Lich King to enable a targeted strike against the Scarlet Vanguard.

Input Format

Line $1$: Four integers $n$, $m$, $a$, $b$, meaning the legion matrix has $n$ rows and $m$ columns. There are $a$ infection sources, and $b$ is the number of lords in the Scarlet Vanguard.

The next $a$ lines: Each line has two integers $x$, $y$, indicating an infection source at row $x$, column $y$.

The next $b$ lines: Each line has two integers $x$, $y$, indicating a lord at row $x$, column $y$.

Output Format

Lines $1$ to $b$: Each line contains one integer, the time when that lord becomes infected. The output order matches the input order. If a person’s position is an infection source, then their infection time is $0$.

5 4 2 3
1 1
5 4
3 3
5 3
2 4

3
1
3

Hint

Explanation for Sample 1

As shown below, the infection times for all people, and the positions of infection sources and lords, are marked.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le n, m \le 500$, $1 \le a, b \le 10^5$.

Translated by ChatGPT 5