A. 列队

题目描述

快开学了，小W正在军训。

他们班一共有 $n * m$ 位同学，于是列队的时候，教官让他们站成了 $n$ 排 $m$ 列。小W发现，如果一个人的身高在他所在的那一排是最高的，在那一列也是最高的，那么他会很显眼。由于列队过于无聊，小W开始计算有多少人非常显眼。

这显然难不倒他，于是他想计算有多少人是他所在排第 $x$ 高的，在他所在列是第 $y$ 高的。小W要忙着应付教官了，所以他没有时间来算了，于是他找来了没在军训的你帮他算一算。他可能有很多询问，你需要快速回答所有的询问。

输入格式

第一行三个整数 $n$，$m$，$q$。

接下来 $n$ 行，每行 $m$ 个整数，代表第 $i$ 行第 $j$ 列的整数 $h_{i,j}$ 表示第 $i$ 排第 $j$ 列的人的身高。保证 $[1,n * m]$ 的每个整数出现且仅出现一次。

接下来 $q$ 行，每行两个整数 $x$，$y$，表示一组询问。

输出格式

输出共 $q$ 行，每行一个整数，表示第 $i$ 组询问的答案。

样例1

input

3 3 2
1 8 9
3 2 7
6 5 4
3 3
2 2

output

3
2

explanation

对于第一组询问，$(1,1), (2,2), (3,3)$ 是符合条件的。

样例2

input

3 3 2
1 2 7
6 4 5
8 3 9
3 2
2 3

output

1
2

样例3

见下载文件。

限制与约定

对于 $10\%$ 的数据，$n, m, q \le 100$。

对于另外 $15\%$ 的数据，$n, m \le 100, q \le 10^5$。

对于另外 $20\%$ 的数据，$n, m, q, \le 400$。

对于另外 $5\%$ 的数据，满足 $a_{i,j} = ( i - 1 ) * m + j$。

对于 $100\%$ 的数据，$n, m \le 1000, q \le 5 * 10^5$。

时间限制：1s

空间限制：512MB

下载

样例数据下载