题目描述

我们有一个$n$行$m$列的矩阵，现在小Q有$K$个问题，每次询问一个以$x_1$行$y_1$列为左上角，$x_2$行$y_2$列为右下角的子矩阵的最大值。

输入

第一行三个整数$n,m,K$。$(n,m≤250,K≤10^6)$ 接下去$n$行，每行有$m$个整数，设$a[i][j]$为矩阵$i$行$j$列的数字，保证0≤a[i][j]<2^{31}。 接下去$K$行，每行$4$个整数$x_1,y_1,x_2,y_2$，保证$(x_1≤x_2,y_1≤y_2)$。

输出

共$K$行，每行对应一个答案。

输入样例

3 4 5
789 15225 27847 6452 
3976 18268 23626 1943 
13336 26216 17321 4960 
2 2 3 4
2 3 3 4
2 1 3 4
1 3 2 4
1 2 3 2

输出样例

26216
23626
26216
27847
26216

提示

【数据规模】 对于30%的数据， $n,m≤50，K≤1000$。 对于50%的数据， $n,m≤250，K≤10000$。 对于100%的数据， $n,m≤250，K≤10^6$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。