The matrix of integers aij is given, where 1 ≤ i ≤ n, 1 ≤ j ≤ m. For given lx, ly, rx, ry find

Input

The first line contains the size of the matrix - n, m (1 ≤ n, m ≤ 1000). Next n lines contains m numbers aij (1 ≤ aij ≤ 1000), separated with a space. The line number n + 2 contains number of queries q (1 ≤ q ≤ 106). In the next q lines the queries are given lxi, lyi, rxi, ryi (1 ≤ lxi ≤ rxi ≤ n, 1 ≤ lyi ≤ ryi ≤ m).

Output

Print q numbers in separate lines - the answers to the queries.