Two-Dimensional Range Sum

An $N \times N$ table is filled with $N \times N$ numbers. Write a program that computes the sum of the entries from $(x_1, y_1)$ to $(x_2, y_2)$. Here $(x, y)$ means row $x$, column $y$.

For example, take $N = 4$ and the table below.

The sum from $(2, 2)$ to $(3, 4)$ is $3+4+5+4+5+6 = 27$, and the sum from $(4, 4)$ to $(4, 4)$ is $7$.

Given the numbers in the table and the sum queries, write a program that answers them.

The first line contains the table size $N$ and the number of sums to compute, $M$. ($1 \le N \le 1024$, $1 \le M \le 100000$)

Each of the next $N$ lines holds one row of the table, starting from row 1. A line lists the $N$ numbers of that row, starting from column 1. Every number in the table is a natural number no larger than 1,000.

Each of the next $M$ lines holds four integers $x_1$, $y_1$, $x_2$, $y_2$. ($1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le N$)

Print $M$ lines. On each line print the sum from $(x_1, y_1)$ to $(x_2, y_2)$, one per query, in input order.