题目描述

给你一个$n \times n$二维数组A（$|A| \leq 10^5$），对于这个数组，会有Q次询问，每次询问会输入$x_l,x_r,y_l,y_r$($x_l\leq x_r,\ \ y_l\leq y_r$)，你需要计算出$\sum^{x_r}_{i=x_l} \sum^{y_r}_{j=y_l} \ \ A_{i,j}$的结果（也就是左上角坐标为（$x_l,y_l$），右下角坐标为（$x_r,y_r$），边与$x$轴或$y$轴的子数组的和）

输入格式

输入的第一行包含两个个正整数 $n$和$Q$ 。

第二行到第$n+1$行包含 $n$ 个整数，第i行分别为 $A_{i1}, a_{i2}, \cdots a_{in}$ 。

接下来$Q$行，每行包含$4$个正整数，分别是$x_l,y_l,x_r,y_r$

输出格式

每行输出一个非负整数，其中第$i$行表示第$i$次查询的答案。

样例 #1

样例输入 #1

3 5
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
1 1 3 3
1 2 2 3
2 3 3 3

样例输出 #1

12
28
45
16
15

提示

对于 $50 \%$ 的数据, $1 \leq n \leq 50,1 \leq Q \leq 1000$ 。

对于$100\%$的数据, $1 \leq n \leq 1000 ,1 \leq a_{i} \leq 1000 ,1 \leq Q \leq 10^6$ 。

该题读入量较大，请使用更快的读入方式