Given an grid $A$ with size $N \times M$. The cell on the $i^{th}$ row $j^{th}$ column is denoted as $(i, j)$.
If $A_{i, j} > 0$, then $(i, j)$ is a walkable cell. Otherwise, if $A_{i, j} = 0$, then $(i, j)$ is an obstacle cell and cannot be passed through. It is given that there are $K$ obstacle cells in the grid. Please note that the boundary of the grid are all obstacle cells.
We define $walk(X, Y, C)$ as follows:
- Initially, you are located at $(X, Y)$, facing east. You will perform $C$ moves.
- A move is as follows:
- Let the cell you are currently facing be $(X_1, Y_1)$.
- If $(X_1, Y_1)$ is a walkable cell, you walk to it, and this move ends.
- Otherwise, you will turn to your right side by $90$ degrees, and this move ends.
- After all moves, your journey ends. Denote the position you end to be $(E_X, E_Y)$. Then, $walk(X, Y, C)$ returns $A_{E_X, E_Y}$.
You imagined $Q$ scenarios. For the $i^{th}$ scenario, you will be given four integers $X_i, Y_i, L_i$ and $R_i$.
Your task is to decide the value of $C$, such that $L_i \le C \le R_i$ and $walk(X_i, Y_i, C)$ is mazimized. Output the maximum value of $walk(X_i, Y_i, C)$.
Input
The first line contains three integers $N, M$ and $K$.
For the following $N$ lines, each line contains $M$ integers, denoting the grid. The integer on the $i^{th}$ line $j^{th}$ column denotes $A_{i, j}$.
The next line contains an integer $Q$, denoting the number of scenarios.
For the following $Q$ lines, the $i^{th}$ line contains four integers $X_i, Y_i, L_i$ and $R_i$, denoting the $i^{th}$ scenario.
Output
Output $Q$ lines, the $i^{th}$ line contains the answer to the $i^{th}$ scenario.
Subtasks
For all test cases:
- $1 \le N, M \le 5 \times 10^5$
- $0 \le K < N \times M \le 5 \times 10^5$
- $0 \le A_{i, j} \le 10^9$ for $1 \le i \le N$, $1 \le j \le M$
- $1 \le Q \le 3 \times 10^5$
- For all $i$ such that $1 \le i \le Q$:
- $1 \le X_i \le N$
- $1 \le Y_i \le M$
- $0 \le L_i \le R_i \le 10^9$
Additional Constraints on Subtasks $1-6:$
- $1 \le N \times M \le 10^5$
- $1 \le Q \le 10^5$
| Subtask | Score | Additional Constraints |
|---|---|---|
| $1$ | $9$ |
$N = 1$ $Q \le 10$ $K = 0$ $L_1 = R_1 < M$ |
| $2$ | $12$ |
$Q \le 10$ $R_1 \le 10^6$ |
| $3$ | $17$ | $Q \le 10$ |
| $4$ | $13$ |
$L_i = R_i \ge 10^7$ for $1 \le i \le Q$ $K = 0$ |
| $5$ | $13$ | $L_i = R_i \ge 10^7$ for $1 \le i \le Q$ |
| $6$ | $12$ | $L_i \ge 10^7$ for $1 \le i \le Q$ |
| $7$ | $16$ |
$N \times M \le 10^5$ $Q \le 10^5$ |
| $8$ | $8$ | No Additional Constraints |
Sample Test Cases
| Input | Output | |
|---|---|---|
| 1 5 0 5 4 3 2 1 2 1 2 2 2 1 5 4 4 |
2 3 |
|
This test case satisfies the special constraints of subtask $1$. For the first scenario, you start at $(1, 2)$ and can only choose $C = 2$. After performing $2$ moves, you end up at $(1, 4)$. As this is the only possibility, simply output $A_{1, 4}=2$. For the second scenario, you start at $(1, 5)$ and can only choose $C = 4$. For the first two moves, as you are facing outside the boundary, you turn $90$ degrees to the right. Then, you walk to your front by $2$ times and end up at $(1, 3)$. |
||
| 2 5 4 6 0 3 2 0 5 0 9 4 0 3 1 3 0 1 1 4 1 4 2 1 0 3 |
3 9 5 |
|
| 4 4 0 9 1 4 7 7 6 2 1 3 5 6 2 1 3 2 1 5 1 1 1 1 1 1 2 2 1 1 4 4 1 1 8 8 1 1 16 16 |
1 4 7 1 9 |
|
Scoring: Per Subtask
Authored by s22f26
Appeared in 2026 Mini Comp 5 (Pre-HKSC)