A spiral on a grid of size (2n+1)×(2n+1) has been con- structed as follows. Number 1 is in the center square at (0, 0), number 2 is to the right of it at (1, 0), and then we continue place the positive integers in order along the spiral in counterclockwise fashion. Now, given 2 coordinates indi- cating 2 corners of a rectangle, find the sum of all numbers in the enclosing rectangle. See the figure on the right for example. Input A number of of inputs (≤ 100), each starting with line contains two integers n (1 ≤ n ≤ 109) and q (1 ≤ q ≤ 100): the size of the grid and the number of queries. After this, there are lines, each containing four integers (x1, y1) and (x2, y2) in that order, where −n ≤ x1, y1, x2, y2 ≤ n. This is the 2 corners of the rectangle, in cartesian 2D coordinates. See the diagram, 1 is at the center at (0, 0). Output For each input, output the answer modulo 1000000007. Sample Input 23 0 -2 1 1 -1 0 1 0 1212 Sample Output 74 9 14