격자 속의 숫자

모든 자연수를 아래처럼 빈칸 없이 왼쪽부터 오른쪽으로 차례대로 1부터 나열한 문자열 S를 생각하자.

12345678910111213141516171819202122232425···

S와 관련된 문제는 이 세상에 이미 많이 있다. 최근의 어떤 필기시험에서는 S의 2 · 106번째 자리를 손으로 구하는 문제가 출제된 바 있다.

문자열 S는 가로로 무한히 길쭉하지만, 이 문제가 인쇄된 종이나 이 문제가 띄워져 있는 모니터는 가로 폭이 고정되어 있다. 만약 S를 모든 숫자의 글자 폭이 동일한 글꼴로 인쇄하거나 적절한 편집기로 읽는다면, 아래와 같이 모든 줄에 M개의 숫자가 순서대로 나타나 있는 형태가 될 것이다.

이러한 방식으로 S의 첫 109 · M글자를 109 × M 크기의 행렬 A에 순서대로 썼다고 하자. 위의 그림에는 M = 31일 때 A의 1행부터 7행까지가 나타나 있다.

2차원 행렬이 있으니, 왠지 2차원 부분합을 구하고 싶지 않은가? 행렬 A의 직사각형 영역 [r1, r2] × [c1, c2]이 주어질 때, 이 영역에 포함된 숫자들의 합, 즉

$\sum\_{i=r\_1}^{r\_2} \sum\_{j=c\_1}^{c\_2} A\_{i,j}$

의 값을 구하는 프로그램을 작성하라. 한 번만 구하기는 아쉬우므로, Q번 구하도록 하자.

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

다음 Q개의 줄에는 네 개의 정수 r1, c1, r2, c2(1 ≤ r1 ≤ r2 ≤ 109, 1 ≤ c1 ≤ c2 ≤ M)이 주어진다.

각각의 질의마다 $\sum\_{i=r\_1}^{r\_2} \sum\_{j=c\_1}^{c\_2} A\_{i,j}$의 값을 한 줄에 하나씩 순서대로 출력한다.