Description

事实上，宇宙中可以看到的物质只占宇宙总质量的不到10%，剩下的90%多是看不见摸不着的暗物质。暗物质能量惊人，是星际航行中无穷无尽强大动力的来源，而魔法世界的魔法实际上也是利用了围绕在我们四周但我们却毫无察觉的暗物质能量。现在，为了阻击修罗王的机器人军团，魔法世界使用了暗物质能量炮，暗物质能量炮攻击范围是一个矩形，攻击后可以使该范围内的机器人全部失灵。已知机器人军团在一个n * m二维的矩阵中，矩阵中的各元素数代表该处的机器人数量，系统预设了q种攻击，每次攻击都是攻击一个小矩阵，即每次攻击时先确定矩阵的左上角坐标Li(行号),Lj(列号),再确定右下角坐标Ri(行号),Rj(列号)。现在请帮忙预估出q种攻击中，每次摧毁的机器人数量。

Input Format

第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 ti,tj, bi,bj，表示一组询问。
【数据范围】
1≤n,m≤1000,
1≤q≤200000,
1≤Li≤Ri≤n,
1≤Lj≤Rj≤m,
1≤ 矩阵内元素的值 ≤1000

Output Format

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

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

17
27
21

Source

动态规划