B21 例题-5 子矩阵之和

题目描述

给出 $n\times m$ 的矩阵。有 $k$ 次询问，每次求左上角坐标为 $x_a,y_a$ ，右下角坐标为 $x_b,y_b$ 的子矩阵中元素的和。

输入格式

第一行三个正整数 $n,m,k$ ，分别表示矩阵的行、列数以及询问的次数；

接下来的 $n$ 行，每行 $m$ 个正整数，描述该矩阵；

接下来 $k$ 行询问，每行四个正整数$x_a,y_a,x_b,y_b$ ，表示询问的子矩阵的左上角坐标和右下角坐标。

输出格式

共 $k$ 行，每行一个整数，表示询问的子矩阵数字之和。

样例输入

3 4 2
8 4 10 15
9 12 3 5
11 5 7 4
3 2 3 3
1 1 3 2

样例输出

12
49

数据范围

对于 $100\%$ 的数据： $1\le n,m\le 500$，$1 \le k\le 1000$，$1 \le v_{i,j}\le 1000$，$1 \le x_a,x_b\le n$，$1 \le y_a,y_b\le m$ 。