N×N 크기의 2차원 배열(표)에 정수가 채워져 있다.

이때, 표의 특정 사각형 영역 (x1, y1)부터 (x2, y2)까지 포함되는 수들의 합을 구하는 프로그램을 작성하시오.

표의 행과 열 인덱스는 1부터 시작한다. (즉, 가장 왼쪽 위 좌표는 (1, 1)이다.)

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 Q가 공백을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 표에 채워져 있는 N개의 정수가 공백으로 구분되어 주어진다.

그다음 줄부터 Q개의 줄에 걸쳐 합을 구해야 하는 사각형 영역을 의미하는 네 정수 x1, y1, x2, y2가 공백을 사이에 두고 주어진다.

출력

Q개의 줄에 걸쳐, 각 줄마다 입력으로 주어진 (x1, y1)부터 (x2, y2)까지의 사각형 영역에 포함된 수들의 합을 출력한다.

제약 조건

1 ≤ N ≤ 1000

1 ≤ Q ≤ 100000

-1000 ≤ 표 안의 수 ≤ 1000

1 ≤ x1 ≤ x2 ≤ N

1 ≤ y1 ≤ y2 ≤ N

예제 입력 1

4 3
5 -2 8 1
-3 4 2 7
1 9 -5 3
6 0 4 -1
2 2 3 4
1 1 2 2
1 3 4 4

예제 출력 1

20
4
19