나선 격자의 직사각형 합

시간 제한1.5초메모리 제한256 MB

요약

중심에 1을 두고 반시계 방향 나선으로 채운 (2n+1)x(2n+1) 격자에서, 축에 나란한 직사각형 안 수의 합을 1e9+7로 나눈 나머지를 q개 질의에 답한다.

난이도: 어려움10점 중 8점
유형: 수학, 구현, 누적 합, 정수론
정답자: 아직 제출이 없습니다

문제

크기가 $(2n+1) \times (2n+1)$ 인 격자를 다음과 같이 채운다. 가운데 칸에 $1$ 을 적고, 그 오른쪽 칸에 $2$ 를 적은 다음, 반시계 방향으로 나선을 그리며 이어지는 수를 차례로 적는다.

칸의 위치는 정수 좌표 $(x, y)$ 로 나타낸다. 가운데 칸이 $(0, 0)$ 이고, $x$ 는 오른쪽으로 갈수록 커지며 $y$ 는 위로 갈수록 커진다. 그래서 격자의 모든 칸은 $-n \le x \le n$ 과 $-n \le y \le n$ 을 만족한다. $n = 2$ 인 격자는 이렇게 채워진다.

	$x=-2$	$x=-1$	$x=0$	$x=1$	$x=2$
$y=2$	17	16	15	14	13
$y=1$	18	5	4	3	12
$y=0$	19	6	1	2	11
$y=-1$	20	7	8	9	10
$y=-2$	21	22	23	24	25

직사각형 영역 $q$ 개가 주어진다. 각 영역에 들어 있는 수의 합을 $10^9+7$ 로 나눈 나머지를 구하라.

입력

첫째 줄에 격자의 크기 $n$ 과 질의의 개수 $q$ 가 주어진다.

이어지는 $q$ 개 줄에 각각 네 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 주어진다. 이는 두 꼭짓점 $(x_1, y_1)$ 과 $(x_2, y_2)$ 가 정하는 직사각형 영역, 즉 $x_1 \le x \le x_2$ 와 $y_1 \le y \le y_2$ 를 만족하는 칸 전체를 뜻한다.

출력

질의마다 한 줄에 그 영역에 들어 있는 수의 합을 $10^9+7$ 로 나눈 나머지를 출력한다.

제한

$1 \le n \le 10^9$
$1 \le q \le 100$
$-n \le x_1 \le x_2 \le n$
$-n \le y_1 \le y_2 \le n$

예제2

예제 1
입력
```
2 3
0 -2 1 1
-1 0 1 0
1 2 1 2
```
예상 출력
```
74
9
14
```

예제 2

입력

1 9
-1 1 -1 1
0 1 0 1
1 1 1 1
-1 0 -1 0
0 0 0 0
1 0 1 0
-1 -1 -1 -1
0 -1 0 -1
1 -1 1 -1

예상 출력