矩形计算

给定一个 $n\times m$ 的整数矩阵，以及 $q$ 次询问。每次询问给出一个子矩阵，要求计算该子矩阵的权值。

对于子矩阵中的每一种整数 $x$，若 $x$ 在该子矩阵中出现了 $p$ 次，则它对该子矩阵权值的贡献为 $p^2$。子矩阵的权值等于其中所有不同整数的贡献之和。

输入格式

第一行包含两个整数 $n,m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示矩阵中的元素。

随后一行包含一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行包含四个正整数 $x_1,y_1,x_2,y_2$，表示询问以第 $x_1$ 行第 $y_1$ 列的元素和第 $x_2$ 行第 $y_2$ 列的元素为对角顶点的子矩阵的权值。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

样例输入

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

样例输出

8
4
38
1
8
12
27
4

数据范围

• 对于全部数据，$1\le n,m\le 200$；
• $q\le 10^5$；
• 矩阵中每个元素的绝对值不超过 $2\times 10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

8
4
38
1
8
12
27
4