Se ha construido una cuadrícula de tamaño ~(2n+1) \cdot (2n+1)~ de la siguiente manera. El número ~1~ se ha colocado en el cuadro central, el número ~2~ se ha colocado a la derecha de él y los siguientes números se han colocado a lo largo de la espiral en sentido contrario a las agujas del reloj.

Tu tarea es calcular las respuestas para ~q~ consultas, donde se solicita la suma de los números en una región rectangular en la cuadrícula (módulo ~10^9+7~). Por ejemplo, en la siguiente cuadrícula con ~n=2~, la suma de los números en la región gris es ~74~:

Entrada:

La primera línea de entrada contiene dos enteros ~n~ y ~q~: el tamaño de la cuadrícula y el número de consultas.

Después de esto, hay ~q~ líneas, cada una conteniendo cuatro enteros ~x_1~, ~y_1~, ~x_2~ y ~y_2~ (~-n \leq x_1 \leq x_2 \leq n~, ~-n \leq y_1 \leq y_2 \leq n~). Esto significa que debes calcular la suma de los números en una región rectangular con esquinas ~(x1, y1)~ y ~(x2, y2)~.

Salida:

Debes imprimir la respuesta para cada consulta (módulo ~10^9+7~).

Subtareas:

En todas las subtareas ~1 \leq q \leq 100~.

Subtarea 1 (12 puntos): ~1 \leq n \leq 1000~

Subtarea 2 (15 puntos): ~1 \leq n \leq 10^9~, ~x_1=x_2~ y ~y_1=y_2~

Subtarea 3 (17 puntos): ~1 \leq n \leq 10^5~

Subtarea 4 (31 puntos): ~1 \leq n \leq 10^9~ y ~x_1=y_1=1~

Subtarea 5 (25 points): ~1 \leq n \leq 10^9~

Entrada Ejemplo:

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

Salida Ejemplo:

74
9
14