题目描述

在一个 $n\times m$ 的网格上每个格子都有颜色，$q$ 次询问，每次询问只保留 $l$ 至 $r$ 列时有多少个四连通的颜色块。两个格子同色但不连通算在不同的颜色块内。

输入格式

第一行三个整数 $n,m,q$，$1\le n\le 10$，$1\le m,q\le 10^5$。

接下来 $n$ 行，每行 $m$ 个整数，描述网格颜色信息，每一个整数不超过 $10^6$。

接下来 $q$ 行，每行两个整数 $l,r$，$1\le l\le r\le m$。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5

6
7
3
4