题目描述

智利安第斯山脉越来越受到背包客和徒步旅行者的欢迎。山脉中的许多地区十分偏远，因此也很危险。旅游部门希望帮助旅行者规划行程，尤其希望他们事先知道旅途中必须攀登到的最高海拔，以决定需要携带哪些装备。

给定一幅由二维高度网格表示的地形图，以及若干组起点和终点。

登山者可以从一个格子移动到上下左右四个相邻格子。对于每位登山者，请求出为了从起点到达终点，他至少必须能够到达多高的海拔。

换句话说，在所有从起点到终点的路径中，最小化路径经过格子的最大高度，并输出这个最小值。

输入格式

输入包含：

• 第一行三个整数 $m,n,q$（$1\le m,n\le500$，$1\le q\le10^5$），分别表示地图的行数、列数和询问数量；
• 接下来 $m$ 行，每行 $n$ 个整数 $h_1,h_2,\ldots,h_n$（$1\le h_i\le10^6$），表示各格子的高度；
• 接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$（$1\le x_1,x_2\le m$，$1\le y_1,y_2\le n$），表示一位登山者希望从 $(x_1,y_1)$ 前往 $(x_2,y_2)$。

左上角格子的坐标为 $(1,1)$，右下角格子的坐标为 $(m,n)$。

输出格式

按照输入中询问的顺序，输出 $q$ 个整数，每个整数表示对应登山者完成旅程所必须能够到达的最低最大高度。

每个答案可以输出在单独一行；使用任意空白字符分隔均可。

样例

输入

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

输出

2
4
3