数据核心

题目描述

有一个 $n$ 行 $m$ 列的矩阵，有 $q$ 次询问，每次询问给出 $x, y$，求以 $(x, y)$ 为左上角能得到的最大子矩阵。

输入格式

第一行输入 $n, m$。

接下来 $n$ 行，每行 $m$ 个整数 $a_{i, j}$ 表示该矩阵。

接下来一行输入一个整数 $q$。

最后 $q$ 行，每行两个整数 $x_i, y_i$ 表示第 $i$ 次询问所对应的 $x, y$。

输出格式

共 $q$ 行，第 $i$ 行一个整数 $ans_i$ 表示第 $i$ 次询问的结果。

样例

样例输入 #1

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

输出样例 #1

16
12
7
2
4
-1

样例解释 #1

数据范围

对于 $100 \%$ 的数据，$1 \le n \times m, q \le 10 ^ 6, 1 \le a _ {i, j} \le 10 ^ 9$。