Spiral Grid Region Sum

A grid of size \((2n+1)\times(2n+1)\) is constructed as follows. Number \(1\) is placed in the center square, number \(2\) is placed to its right, and the following numbers are placed along a spiral in the counterclockwise direction.

Your task is to answer \(q\) queries. In each query, you are given a rectangular region of the grid defined by its top-left and bottom-right coordinates, and you must calculate the sum of the numbers in that region modulo \(10^9+7\).

Note: The grid is 0-indexed; the top-left cell is \((0, 0)\) and the bottom-right cell is \((2n, 2n)\).

inputFormat

The first line contains two integers \(n\) and \(q\) where \(n \ge 0\) and \(q \ge 1\). The grid has size \((2n+1)\times(2n+1)\).

Each of the next \(q\) lines contains four integers \(r_1, c_1, r_2, c_2\) (with \(0 \le r_1 \le r_2 \le 2n\) and \(0 \le c_1 \le c_2 \le 2n\)), representing the top-left and bottom-right coordinates of a rectangular region.

outputFormat

For each query, output a single integer: the sum of the numbers in the specified rectangular region modulo \(10^9+7\).

sample

1 2
0 0 1 1
1 1 2 2

16
20