N × N 크기의 표가 있고, 각 칸에는 하나의 수가 적혀 있다.

이 표에서 직사각형 모양의 일부 영역을 여러 번 지정하려고 한다.
하나의 영역은 왼쪽 위 칸의 위치 (x1, y1)과 오른쪽 아래 칸의 위치 (x2, y2)로 주어진다.
여기서 (x, y)는 x행 y열을 의미한다.

각 요청마다, 지정된 직사각형 영역 안에 들어 있는 모든 수의 합을 구해야 한다.

표에 적힌 수와 여러 개의 영역 정보가 주어졌을 때, 각 영역의 합을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다.

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.

다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2가 주어진다.
이는 (x1, y1)부터 (x2, y2)까지의 영역을 의미한다.

표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다.

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지의 합을 구해 출력한다.

제한

• 1 ≤ N ≤ 1024
• 1 ≤ M ≤ 100,000
• x1 ≤ x2
• y1 ≤ y2

예제 입력 1

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1

27
6
64

예제 입력 2

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2

1
2
3
4