← 返回题目列表

Codeforces · 811/E

E. 弗拉迪克和有趣的旗帜

中文机器翻译题面 查看原题

弗拉迪克在业余时间估计了旗帜的美丽。

每个标志都可以表示为由正整数组成的矩阵 n × m。

让我们将标志的美丽定义为其矩阵中的组件数量。我们将组件称为一组具有相同编号的单元格,并且在该组中的任何一对单元格之间都存在一条穿过来自同一组件的相邻单元格的路径。以下是将一些标志矩阵划分为多个组件的示例:

但这一次他决定改变这个过程中的一些事情。现在他想要估计的不是整个旗帜,而是某些部分。标志段可以描述为标志矩阵的一个子矩阵,其对角位于 (1, l) 和 (n, r),其中满足条件 1 ≤ l ≤ r ≤ m。

帮助 Vladik 计算给定标志的某些片段的美度。

输入

第一行包含三个空格分隔的整数 n、m、q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) - 分别是标志矩阵的维度和段数。

接下来的 n 行中的每一行都包含 m 个空格分隔的整数——标志矩阵的描述。标志矩阵的所有元素均为不超过106的正整数。

接下来的 q 行包含两个空格分隔的整数 l, r (1 ≤ l ≤ r ≤ m) - 美女 Vladik 想知道的线段边界。

输出

对于每个段,在相应的行上打印结果。

示例

输入 #1

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

输出 #1

6
7
3
4

注意

对第一个测试用例中每个段的组件进行分区: