Background

The Lich King’s Scourge has returned in force. The Scarlet Crusade organized a vanguard to sail to Northrend to fight the Scourge and any creature tainted by undeath. Isolated from both the Alliance and the Horde, the Scarlet Vanguard was soon surrounded by the Scourge. They gathered their main forces to resist the encirclement. Terrifyingly, some of them have been infected by the undead plague. If the spread is not stopped, annihilation is imminent. Highlord Abbendis has begun investigating the source of the plague. It turns out there is a traitor within the Scarlet Vanguard who has defected to the Scourge, seeking to convert the entire Scarlet Vanguard into the Scourge! Do not be surprised—you are that traitor. Before your identity is exposed, you must quickly complete the task assigned to you by the Lich King.

Problem 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