蔬菜

vegetable.cpp/in/out

• 时间限制：1s
• 内存限制：512MB

题目描述

小 C 在家中开垦了一块菜地，可以抽象成一个 $r \times c$ 大小的矩形区域，菜地的每个位置都种着一种蔬菜。秋天到了，小 C 家的菜地丰收了。

小 C 拟定了 $q$ 种采摘蔬菜的计划，计划采摘区域是菜地的一个子矩形，你需要帮助他计算每种计划的美味度，美味度等于每种蔬菜在采摘区域出现次数的平方和。

输入格式

第一行三个正整数 $r, c, q$。

接下来 $r$ 行每行 $c$ 个正整数，第 $i+1$ 行第 $j$ 个数为 $a_{i,j}$，表示每个位置的蔬菜种类。

接下来 $q$ 行，每行 4 个正整数 $x_0, y_0, x_1, y_1$ 表示采摘区域的左上角和右下角的位置。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 组采摘计划的答案。

样例输入

3 4 8
1 3 2 1
1 3 2 4
1 2 3 4
1 1 2 2
1 1 2 1
1 1 3 4
1 1 1 1
2 2 3 3
2 2 3 4
1 1 3 3
2 4 3 4

样例输出

8
4
38
1
8
12
27
4

数据范围

对于 100% 的数据，$r, c \le 200$，$q \le 100000$，$a_{i,j} \le 10^9$。

• Subtask 1 (23pts)：$r, c \le 100$，$q \le 1000$。
• Subtask 2 (15pts)：$r, c \le 100$，$q \le 10000$。
• Subtask 3 (17pts)：$r, c \le 200$，$q \le 50000$。
• Subtask 4 (20pts)：蔬菜种类数不超过 200。
• Subtask 5 (25pts)：无特殊限制。