题目描述

有一个 $n \times n$ 的蛇形数组 a，当 $n = 4$ 时，数组如下：

  1  2  3  4
 12 13 14  5
 11 16 15  6
 10  9  8  7

给出 $q$ 次查询，每次查询给出 $4$ 个整数 x1, y1, x2, y2，要求计算出蛇形数组里 a[x1][y1] ... a[x2][y2] 范围内的数字的和。

格式要求

输入格式

第一行输入 $2$ 个整数 $n, q(1 \leq n \leq 10^3, 1 \leq q \leq 10^4)$。

接下来 $q$ 行，每行 $4$ 个整数 $x_1, y_1, x_2, y_2(1 \leq x_1 \leq x_2 \leq n$$, 1 \leq y_1 \leq y_2 \leq n)$。

输出格式

输出 $q$ 行，每行 $1$ 个整数，代表对应的和。

样例

4 2
1 1 1 4
2 2 3 4

10
69