MATRIX的查询

题目描述

今天AZY来谈谈matrix，没见过这个单词的同学（如果有的话）请自行查词典。

嗯，虽然黑客帝国很好看，但这次要说的不是这个电影，而是Linear Algebra中的“矩阵”。

Given a m×n matrix，求其任意子矩阵中不同数字的个数。

输入

多组测试数据。 对于每组数据，第一行为三个整数m，n，t（1≤m,n≤500，1≤q≤100000），表示矩阵的大小为m×n，且有t组查询。

接下来m行，每行n个元素，用空格隔开，为对应的数字矩阵M，其中0 ≤ Mij ≤ 9。

再接下来t行，每行四个整数x1，y1，x2，y2，为一次查询，表示子矩阵的左上角坐标为(x1,y1)，右下角坐标为(x2,y2)。坐标代表二维数组的第几行第几列。（保证数据合理，具体见样例）

输出

对于每组测试数据，输出对应这组数据的每次查询的结果。

输入样例

3 3 3 
1 2 3
3 2 1
5 6 3
1 1 2 3
2 2 2 2
1 1 3 3

输出样例

3
1
5

Hint & Warning

数据量很大，请用scanf & printf，否则可能超时。

数据量很大，请用scanf & printf，否则可能超时。

数据量很大，请用scanf & printf，否则可能超时。

二维随机变量的分布函数满足这样一些性质（图片来自上海交通大学数学系概率统计课程教学课件）：

AZY知道你们对于概率统计这门课还没什么概念，——Please just pay attention to 图中那个“矩阵”以及最后几行那个式子。

此题考查多维数组的综合操作，此题的具体实现与概率没有任何关系。