F. 前缀和矩阵

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

给定一个 $n×m$ 列的矩阵数列以及 $k$ 次询问，每次询问给出四个数 $x_1,y_1,x_2,y_2$ 表示以这两个点为一个矩形的左上角和右下角，可以从矩阵中画出一个子矩阵，求这个子矩阵中所有数的和。

第一行包含三个整数 $n，m，k$

接下来 $n$ 行，每行包含 $m$ 个整数。

接下来 $k$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ ，表示一组询问。

共 $k$ 行，每行输出一个询问的结果。

$1≤n,m≤1000, 1≤k≤2×10^5, 1≤x_1≤x_2≤n, 1≤y_1≤y_2≤m$

$-1000≤$ 矩阵内元素的值 $≤1000$