Problem: Painting the Grid

Problem Description

You are given a 2D grid with **n** rows and **m** columns. Initially, all cells in the grid are white, except for a single cell **(R₀, C₀)** which is already painted black.

You will receive **n × m - 1** queries. In each query, you are given a cell **(Rᵢ, Cᵢ)** that is currently white. Your task is to find the shortest Manhattan distance from this cell to any cell that is currently black. After computing this distance, the queried cell is painted black.

The Manhattan distance between two cells **(x₁, y₁)** and **(x₂, y₂)** is defined as |x₁ - x₂| + |y₁ - y₂|.

You may process the queries in any order (offline solution is allowed). Your goal is to answer all queries efficiently.

Input Format

• The first line contains two integers **n** and **m** — the number of rows and columns of the grid.
• The second line contains two integers **R₀** and **C₀** — the row and column indices of the initially black cell (0-indexed).
• The next **n × m - 1** lines each contain two integers **Rᵢ** and **Cᵢ** — the row and column indices of the cell queried at step **i** (0-indexed). All queried cells are distinct and initially white.

Output Format

For each query, output a single integer — the shortest Manhattan distance from the queried cell to any black cell at the time of the query.

Constraints

• 1 ≤ n, m
• n × m ≤ 200,000
• 0 ≤ R₀ < n, 0 ≤ C₀ < m
• For each query: 0 ≤ Rᵢ < n, 0 ≤ Cᵢ < m
• All queried cells are distinct and different from the initial black cell.

Examples

Example 1

**Input:**

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

**Output:**

2
2
2
2
1
1
1
1

**Explanation:**

• Initially, only (1,1) is black.
• Query 1: (0,0) → distance to (1,1) = |0-1| + |0-1| = 2. Then (0,0) becomes black.
• Query 2: (2,2) → distance to nearest black: min(distance to (1,1)=2, distance to (0,0)=4) = 2. Then (2,2) becomes black.
• Query 3: (0,2) → distance to nearest black: min(distance to (1,1)=2, distance to (0,0)=2, distance to (2,2)=2) = 2.
• And so on.

Example 2

**Input:**

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

**Output:**

1
4
1
2
3
2
1

Notes

• The Manhattan distance between cells (r₁, c₁) and (r₂, c₂) is |r₁ - r₂| + |c₁ - c₂|.
• An offline solution is allowed, meaning you can reorder the queries if needed.
• Suggested approach: Use square-root decomposition. Maintain a cache of answers from a multi-source BFS (run periodically). For each query, compute the answer as the minimum of:

1. The distance from the cached BFS (precomputed distances from all black cells at the time of the last BFS).
2. The distances to a small list of recently added black cells (size ≤ √(n×m)).

When the list of recent black cells reaches √(n×m), clear it and run a new multi-source BFS from all black cells to update the cache.