Building View Score

You are given an N x N grid representing the heights of buildings and Q queries. Each query specifies a sub-grid via four integers r1, c1, r2, c2 (1-indexed). Your task is to compute the sum of building heights within each sub-grid.

The problem can be solved efficiently using a prefix sum matrix. In this approach, you precompute a matrix such that each cell prefix[i][j] represents the sum of the rectangle from (1, 1) to (i, j). With this matrix, the sum of any sub-grid can be computed in constant time using the formula:

\[ \text{score} = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] \]

Write a program that reads the grid and queries from stdin and outputs the result for each query to stdout.

inputFormat

The first line contains two integers N and Q, the side length of the grid and the number of queries.

The next N lines each contains N integers, representing the grid of building heights.

The next Q lines each contains four integers r1, c1, r2, c2 representing a query for the sub-grid.

outputFormat

Output Q lines. Each line should contain an integer representing the sum of building heights within the queried sub-grid.

## sample

1 1
5
1 1 1 1

5

</p>