颜色与方格
题号：NC285796
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小灰灰有 n\times n 只五颜六色的袜子，放在了一个 n 行 n 列方格盒里。

其中第 i 行第 j 列的袜子颜色为 c_{i,j}。

小灰灰眼力有限，只会在一个 K\times K 的范围中查找一双颜色相同的袜子去上课。

小蓝很好奇小灰灰如此邋遢是否能找到合适的袜子，于是她向小灰灰提出了 m 个问题。

第 i 个问题中，小蓝会给出两个整数 x_i,y_i，小灰灰需要回答，在以第 x_i 行第 y_i 列格子为左上角，占据 K 行 K 列的子矩阵中，有多少种颜色可以选出至少一双袜子。

输入描述:

第一行包含三个空格分隔的整数 n, m 和 K。

接下来输入 n 行，每行 n 个整数，第 i 行第 j 列的数表示 c_{i, j}。

接下来 m 行，第 i 行包含两个空格分隔的整数，分别代表 x_i 和 y_i。

保证：
1 \le K \le n \le 700, 1 \le m \le (n - K + 1)^2
1 \le x_i, y_i \le n - K + 1
1 \le c_{i, j} \le 10^6

输出描述:

输出共 m 行，第 i 行代表第 i 次询问的答案。
示例1

输入

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

输出

复制 
3
2
1
2