暂无测试数据。

题目描述

给出一个 \(n\) 行 \(m\) 列的矩阵，
矩阵的每个位置有一个非负整数 \(a[i][j]\)，
有 \(q\) 次询问，
每次询问求一个左上角为 \((a,b)\)，
右下角为 \((c,d)\) 的子矩阵的所有数之和。

输入

第一行两个整数 \(n,m\)，表示矩阵的行和列的大小。
接下来 \(n\) 行每行 \(m\) 个整数，为矩阵内容。
接下来一行为一个整数 \(q\)，表示询问次数。
接下来 \(q\) 行，每行 4 个整数 \(a,b,c,d\)，含义见题面。

输出

共 \(q\) 行，第 \(i\) 行为第 \(i\) 个询问的答案。

样例输入

3 5
1 2 3 4 5
3 2 1 4 7
2 4 2 1 2
3
1 1 3 5
2 2 3 3
1 1 3 3

样例输出

43
9
20

数据范围限制

\(n*m \leq 10^5\)，\(a[i][j] \leq 10^3\)，\(q \leq 100,000\);
\(1 \leq a \leq c \leq n\)，\(1 \leq b \leq d \leq m\);

来源

基础篇补充4.2