Background

一维前缀和：（以第一个元素开始的连续的一段数字的和，即解法中$S_i$）

（题目）给定一个有n个数的序列，其中第i个数为$a_i$, Q次询问，每次询问输入一个正整数$x$ ,输出区间[1,x]的数之和

（解法）设$S_i$为区间1-i的数和，则有递推式$S_i =S_ {i-1} +a_i$ 。即区间[1,i]的数的和，等于区间[1,i-1]的数的和，加上$a_i$ 。设第t次询问输入为x，输出$S_x$即可。

代码见下方example1.cpp

一维差分：

（题目）给定一个有n个数的序列，其中第i个数为$a_i$ ,先有Q次修改操作，每次修改输入3个正整数$x_i, l_i, r_i$ ,表示对区间[$l _i ,r_i$ ]每个数加$x_i$ 在进行完Q次修改之后，有M次询问，每次输入一个正整数x，输出Q次修改后的$a_x$的值。

（解法）开一个辅助数组$t_i$ ,初始时元素都为0。在第i次修改对区间[$l_i ,r_i$]每个数加$x_i$时，对$t_{l_i}$加上$x_i$ , $t_{r_{i}+1}$减去$x_i$ 。在Q次修改之后，设t数组的前缀和为$S_i$ 。求出前缀和数组S，则Q次修改之后第p个位置的数为$a_p+S_p$ 。

代码见下方example2.cpp

二维前缀和：（以位置（1,1）元素为左上角矩阵中数字之和,即解法中$S_{i，j}$)

（题目）给定一个n*m的矩阵a，其中第i行第j列元素为$a_{i,j}$ 。Q次询问，每次给定输入给定$l_i,r_i$ 。求以位置(1,1)为左上角，位置（$l_i, r_i$）为右下角的矩阵区域所有元素之和。

（解法）设$s_{i,j}$为以位置(1,1)为左上角，位置（i,j）为右下角的矩阵区域所有元素之和。则有递推式$s_{i,j} =s _{i-1,j} +s_{i,j-1}- s_{i-1,j-1} + a_{i,j}$ 。对于询问（$l_i ,r _i$），输出$s_{l_i ,r_i}$即可。

(详细说明)$s_{i，j}$ (图中所有区域)=$s_{i,j-1}$ （图中红+浅蓝）+$s_{i-1,j}$ (图中红+深绿)-$s_{i-1,j-1}$（图中红色区域，在前两次相加时被重复计算）+$a_{i,j}$ (图中深蓝)

代码见下方example3.cpp

Description

那么，是否存在二维差分？

即在一个给定的n*m数字矩阵a中，有Q次修改操作，每次输入五个正整数$l_1 ,r_1 ,l_2 ,r_2, x$，表示对以$(l_1 ,r _1）$为左上角，$(l_2 ,r_2)$为右下角的矩阵区域中所有数加上x。Q次操作之后，有M次询问。每次输入两个正整数x、y,输出在Q次修改之后$a_{x,y}$的值。

Format

Input

第一行两个正整数n、m，表示这个矩阵有n行m列。

接下来n行，每行m个整数，其中第i行第j个整数表示$a_{i,j}$。

接下来一行一个正整数Q，表示有Q次修改操作。

接下来Q行，每行5个正整数$l_1,r_1 ,l_2 ,r_2, x$，其含义见问题描述。

接下来一行，一个正整数M，表示有M次询问。

接下来M行，每行两个正整数x,y，其含义见问题描述。

Output

输出m行，每行一个正整数。其中第i行的正整数表示第i次询问的答案。

Samples

3 4
5 8 3 4
3 4 5 8
5 8 3 4
2
1 1 2 2 3
2 3 3 4 6
5
1 3
1 4
3 1
3 2
2 2

3
4
5
8
7

Limitation

本题共有10个测试点，每个测试点10分。

对于30%的测试点，$1\leq n,m \leq 100, 1 \leq Q,M \leq 100$

对于另外40%的测试点，$1\leq n,m \leq 1000, 1\leq Q , M\leq 2000$

对于另外30%的测试点，$1\leq n,m \leq 1000, 1\leq Q , M\leq 10^5$

对于所有测试点，矩阵中的数、以及x的绝对值不超过100。

Code

// example1.cpp
#include <iostream>
using namespace std;
const int N = 100000 + 5;
int a[N], s[N], n, Q;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int x;
        cin >> x;
        cout << s[x] << endl;
    }
    return 0;
}

//example2.cpp
#include <iostream>
using namespace std;
const int N = 100000 + 5;
int n, Q, M, a[N], t[N], s[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        t[l] += x;
        t[r + 1] -= x;
    }
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + t[i];
    cin >> M;
    for (int i = 1; i <= M; i++)
    {
        int x;
        cin >> x;
        cout << s[x] + a[x] << endl;
    }
    return 0;
}

// example3.cpp
#include <iostream>
using namespace std;
const int N = 1000 + 5;
int n, m, Q, s[N][N], a[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << s[l][r] << endl;
    }
    return 0;
}