2차원 구간 합

첫 줄에 격자의 크기 n, m (1 이상 100 이하) 과 질의의 개수 q (1 이상 3000 이하) 가 주어집니다. 이어서 n개의 줄에 각각 m개의 수가 주어집니다. 각 수는 1 이상 1000 이하입니다. 그다음 q개의 줄에 각각 네 정수 r1 c1 r2 c2 가 주어집니다. (1번부터 세며 r1 ≤ r2, c1 ≤ c2.)

각 질의마다 (r1, c1) 부터 (r2, c2) 까지의 직사각형 안에 있는 수의 합을 한 줄에 하나씩 출력하세요.

예시

입력

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

출력

21
11