3724. 求和公式

单点时限: 1.0 sec

内存限制: 256 MB

QQ小方以前不会用 excel 里的求和公式,现在他会了,所以他急切的想教会你。

对于 excel 中的一个子矩阵求和的公式格式是 $sum(A:B)$ ,其中 $A$ 表示子矩阵的左上角坐标, $B$ 表示子矩阵的右下角坐标。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

现在QQ小方会给你一个 $n\times n$ 的正方形矩阵,并且它会将正方形矩阵的两条对角线位置全部填上 $1$ (可以参考下图),其余位置全部填上 $0$ 。并且他给正方形矩阵的行和列从 $0$ 到 $n-1$ 标上了序号。

例如下图所示是 $4\times 4$ 正方形矩阵的填充和行列标号:

现在,为了测试你是否真的掌握了 excel 的矩阵求和公式,QQ小方会进行 $q$ 次询问,每次询问一个子矩阵的和。

输入格式

输入第一行包含两个整数 $n,q(1\le n\le 10^{18},1\le q\le 10^5)$ ,分别表示矩阵的大小和询问的次数。

接下来的 $q$ 行,每行包含四个整数 $a,b,c,d(0\le a\le c< n,0\le b\le d< n)$ ,表示子矩阵。其中子矩阵的左上角坐标为 $(a,b)$ ,右下角坐标为 $(c,d)$ 。

输出格式

输出包含 $q$ 行,针对每一个询问输出一个整数表示答案。

样例

Input
4 2
0 1 1 3
0 0 3 3
Output
3
8

提示

对于样例的第一个询问,红色区域为询问的子矩阵,显然答案为 $3$ 。

253 人解决,369 人已尝试。

313 份提交通过,共有 1825 份提交。

3.3 EMB 奖励。

创建: 5 年,4 月前.

修改: 5 年,4 月前.

最后提交: 1 月,2 周前.

来源: N/A

题目标签