17382번 - 격자 속의 숫자

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

12345678910111213141516171819202122232425···

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

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

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

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

$$\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개의 줄에는 네 개의 정수 r₁, c₁, r₂, c₂(1 ≤ r₁ ≤ r₂ ≤ 10⁹, 1 ≤ c₁ ≤ c₂ ≤ M)이 주어진다.

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