Background

Special for beginners, ^_^

Description

我们有一个n行m列的矩阵，现在小Q有K个问题，每次询问一个以x1行y1列为左上角，x2行y2列为右下角的子矩阵的最大值。

Format

Input

第一行三个整数n,m,K。(n,m≤250,K≤10^6)

接下去n行，每行有m个整数，设a[i][j]为矩阵i行j列的数字，保证0≤a[i][j]<2^31。

接下去K行，每行4个整数x1,y1,x2,y2，保证(x1≤x2,y1≤y2)。

Output

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

Samples

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

Limitation