격자 속의 숫자

모든 자연수를 1부터 순서대로, 빈칸 없이 왼쪽에서 오른쪽으로 이어 붙인 문자열을 $S$라고 하자.

12345678910111213141516171819202122232425···

$S$와 관련된 문제는 이미 많이 있다. 최근의 한 필기시험에서는 $S$의 $2 \times 10^6$번째 자리를 손으로 구하는 문제가 출제되었다.

문자열 $S$는 가로로 무한히 이어지지만, 이 문제가 인쇄된 종이나 이 문제를 띄운 모니터의 가로 폭은 고정되어 있다. $S$를 모든 숫자의 글자 폭이 같은 글꼴로 인쇄하거나 적절한 편집기로 읽으면, 아래와 같이 모든 줄에 $M$개의 숫자가 순서대로 놓이게 된다.

이 방식으로 $S$의 처음 $10^9 \times M$글자를 $10^9 \times M$ 크기의 행렬 $A$에 순서대로 채워 넣었다고 하자. 위 그림은 $M = 31$일 때 $A$의 1행부터 7행까지를 보여 준다.

행렬이 2차원이니 2차원 부분합을 구하고 싶지 않은가? 행렬 $A$의 직사각형 영역 $[r_1, r_2] \times [c_1, c_2]$가 주어지면, 이 영역에 포함된 숫자의 합, 즉 $\sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{i,j}$의 값을 구하는 프로그램을 작성하라. 한 번만 구하기는 아까우니 $Q$번 구하도록 하자.

첫 번째 줄에 정수 $M$($1 \le M \le 100,000$)과 질의의 수 $Q$($1 \le Q \le 1,000$)가 주어진다.

다음 $Q$개의 줄에는 네 개의 정수 $r_1$, $c_1$, $r_2$, $c_2$($1 \le r_1 \le r_2 \le 10^9$, $1 \le c_1 \le c_2 \le M$)가 주어진다.

각 질의마다 $\sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{i,j}$의 값을 입력된 순서대로 한 줄에 하나씩 출력한다.