402385: GYM100741 G Yet Another Median Task

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Yet Another Median Tasktime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
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

加入题单

上一题 下一题 算法标签: