G. Yet Another Median Task
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You're given a matrix a with n lines and n columns. We define the median of an array the element from the middle position of sorted array. If there are two such positions (n is even), get the element whose position is minimal.

Answer q queries of form: what's the median element of a submatrix (x1, y1, x2, y2). Formally, we consider all elements a[i][j] such as x1 <= i <= x2 and y1 <= j <= y2 and add them into a temporary array. Then, get the median of the array.

Input

First line of the input contains numbers n (1 ≤ n ≤ 800) and q (1 ≤ q ≤ 1000). Next n lines contain n numbers, describing the 1-based matrix a. All elements from a can fit into an int type. Next q lines contain numbers x1, y1, x2, y2, describing a query (1 ≤ x1 ≤ x2 ≤ n , 1 ≤ y1 ≤ y2 ≤ n)

Output

Output q lines, each line to answer a query.

Examples
Input
2 4
1 2
2 2
1 1 2 1
1 1 1 2
1 1 2 2
2 2 2 2
Output
1
1
2
2