Một lưới ô vuông kích thước \((2n+1)\text{ x }(2n+1)\) được xây dựng như sau: Số \(1\) sẽ được điền vào ô trung tâm, số \(2\) được điền vào ô bên phải của số \(1\), và những số tự nhiên tiếp theo sẽ được điền 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 về tổng của các số được điền trong một hình chữ nhật con của lưới ô vuông xoắn ốc này (theo modulo \(10^9+7\)). Ví dụ, trong lưới ô vuông dưới đây, \(n=2\) và tổng các số trong hình chữ nhật con được tô màu xám là \(74\):

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) thể hiện kích thước của lưới ô vuông và số lượt 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\) \(\left(-n\leq x_1\leq x_2\leq n, -n\leq y_1\leq y_2\leq n\right)\). Bạn cần tính tổng các số trong hình chữ nhật có hai góc đối là \(\left(x_1, y_1\right)\) và \(\left(x_2, y_2\right)\).

Output

Gồm \(q\) dòng, mỗi dòng ghi một số nguyên là câu trả lời cho truy vấn tương ứng (theo module \(\left.10^9+7\right)\).

Ví dụ

Input

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

Output

74
9
14

Giới hạn

Trong tất cả các test:

• \(1\leq q\leq 100\).
• \(1\leq n\leq 10^9\).

Subtasks

• Subtask 1 (12 điểm): \(1\leq n\leq 1000\).
• Subtask 2 (15 điểm): \(1\leq n\leq 10^9\), \(x_1=x_2\) và \(y_1=y_2\).
• Subtask 3 (17 điểm): \(1\leq n\leq 10^5\).
• Subtask 4 (31 điểm): \(1\leq n\leq 10^9\) và \(x_1=y_1=1\).