4381. [郑轻校赛 2026] 覆盖面积

Problem F. 覆盖面积

给定一个 $n \times m$ 的地图，每个格子有一个整数表示海拔高度。水从水源格子出发，只能流向相邻（上、下、左、右）且海拔小于等于当前格子海拔的格子。

每次询问给出一个水源位置 $(x, y)$，求从该水源出发能够到达的所有格子（包括水源本身）的数量。

Input

第一行包含两个整数 $n,m$ $(1 \le n,m \le 50)$，表示地图的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示每个格子的海拔 $A_{i,j}$ $( -10^9 \le A_{i,j} \le 10^9 )$。

下一行包含一个整数 $q$ $(1 \le q \le 10^6)$，表示询问次数。

接下来 $q$ 行，每行包含两个整数 $x,y$ $(1 \le x \le n,\ 1 \le y \le m)$，表示水源位置。

Output

对于每次询问，输出一个整数，表示能够覆盖的格子数量。

Example

样例输入1

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

样例输出1

2
10
5

Note

下面用红圈表示水源起点，蓝色表示被覆盖的范围：

第一个询问：

第二个询问：

第三个询问：

来源

郑州轻工业大学“筑梯杯”第十八届程序设计大赛暨省内高校邀请赛 F

数据来源：ChenBp