402385: GYM100741 G Yet Another Median Task

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.

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 q lines, each line to answer a query.

2 4
1 2
2 2
1 1 2 1
1 1 1 2
1 1 2 2
2 2 2 2

1
1
2
2