Một bảng ô vuông kích thước \((2n+1) \times (2n+1)\) được xây dựng như sau. Số \(1\) được đặt ở ô chính giữa, số \(2\) được đặt ở ô ngay bên phải nó, và các số tiếp theo được đặt dọc theo một đường xoắn ốc ngược chiều kim đồng hồ.

Nhiệm vụ của bạn là trả lời \(q\) truy vấn. Mỗi truy vấn yêu cầu tính tổng các số trong một vùng hình chữ nhật của bảng, lấy phần dư khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): tham số xác định kích thước bảng và số truy vấn.

\(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\) và \(y_2\), với \(-n \le x_1 \le x_2 \le n\) và \(-n \le y_1 \le y_2 \le n\). Bạn cần tính tổng các số trong vùng hình chữ nhật có hai góc đối diện là \((x_1,y_1)\) và \((x_2,y_2)\).

Dữ liệu ra

Với mỗi truy vấn theo thứ tự trong dữ liệu vào, in ra một dòng chứa kết quả, lấy phần dư khi chia cho \(10^9+7\).

Ràng buộc

Trong mọi phân nhóm, \(1 \le q \le 100\).

Phân nhóm

1. Nhóm 1 (12 điểm): \(1 \le n \le 1000\).
2. Nhóm 2 (15 điểm): \(1 \le n \le 10^9\); mọi truy vấn đều có \(x_1=x_2\) và \(y_1=y_2\).
3. Nhóm 3 (17 điểm): \(1 \le n \le 10^5\).
4. Nhóm 4 (31 điểm): \(1 \le n \le 10^9\); mọi truy vấn đều có \(x_1=y_1=1\).
5. Nhóm 5 (25 điểm): \(1 \le n \le 10^9\).

Ví dụ

2 3
0 -2 1 1
-1 0 1 0
1 2 1 2

74
9
14

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ nhất, bài C.