Sum in a matrix

The matrix of integers a[ij] is given, where 1 ≤ i ≤ n, 1 ≤ j ≤ m. For given l[x], l[y], r[x], r[y] find

Input

The first line contains the size of the matrix - n, m (1 ≤ n, m ≤ 1000). Next n lines contains m numbers a[ij] (1 ≤ a[ij] ≤ 1000), separated with a space. The line number n + 2 contains number of queries q (1 ≤ q ≤ 10^6). In the next q lines the queries are given l[xi], l[yi], r[xi], r[yi] (1 ≤ l[xi] ≤ r[xi] ≤ n, 1 ≤ l[yi] ≤ r[yi] ≤ m).

Output

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

Examples