이차원 구간 합 구하기

$N \times N$개의 수가 $N \times N$ 크기의 표에 채워져 있다. $(x_1, y_1)$부터 $(x_2, y_2)$까지의 합을 구하는 프로그램을 작성하시오. $(x, y)$는 $x$행 $y$열을 뜻한다.

예를 들어 $N = 4$이고 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 $(2, 2)$부터 $(3, 4)$까지의 합은 $3+4+5+4+5+6 = 27$이고, $(4, 4)$부터 $(4, 4)$까지의 합은 $7$이다.

표에 채워진 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

첫째 줄에 표의 크기 $N$과 합을 구해야 하는 횟수 $M$이 주어진다. ($1 \le N \le 1024$, $1 \le M \le 100000$)

둘째 줄부터 $N$개의 줄에 표에 채워진 수가 1행부터 차례대로 주어진다. 각 줄에는 그 행의 수 $N$개가 1열부터 차례대로 주어진다. 표에 채워진 수는 1,000보다 작거나 같은 자연수이다.

다음 $M$개의 줄에는 네 정수 $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$)

총 $M$개의 줄에 걸쳐 $(x_1, y_1)$부터 $(x_2, y_2)$까지의 합을 입력 순서대로 한 줄에 하나씩 출력한다.