该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Miloris和小喵喵是好朋友。Miloris做到了一道套路题：在一个$n*m$的网格上每个格子都有颜色，$q$次询问，每次询问只保留$l$至$r$列时有多少个四连通的颜色块。两个格子同色但不连通算在不同的颜色块内。

她没有看数据范围就想到了一个绝妙的算法于是跑去与小喵喵交流，小喵喵表示他并没有听懂Miloris的做法并抛之脑后。萌萌哒Miloris写出了这个做法并AC了这道题。然而她觉得原题数据范围太水了于是加大了数据范围想考考你。

输入格式

第一行三个正整数$n,m,q$,其中$n,m$表示网格大小，$q$为询问个数。

接下来$n$行，每行$m$个正整数表示该位置颜色$c_{ij}$。

接下来$q$行，每行两个数$l_i,r_i$，表示该次询问的区间左右端点。

输出格式

对于每个询问，输出一行一个整数。

输入输出样例

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

样例 1 解释

数据规模与约定

对于$20\%$的数据，$n,m≤100,q≤1000$；

对于$40\%$的数据，$n,m≤500,q≤1000$；

对于$60\%$的数据，$n,m≤500,q≤20000$；

对于$80\%$的数据，$n,m≤1000,q≤100000$；

对于$100\%$的数据，$10<=n,m≤1000,q≤200000,c_{ij}≤10^9$。