CF811E.Vladik and Entertaining Flags

In his spare time Vladik estimates beauty of the flags.

Every flag could be represented as the matrix n × m which consists of positive integers.

Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:

But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, l) and (n, r), where conditions 1 ≤ l ≤ r ≤ m are satisfied.

Help Vladik to calculate the beauty for some segments of the given flag.

在空闲时间，弗拉基克会评估旗帜的“美观度”。

每面旗帜都可以表示为一个 $ n \times m $ 的矩阵，其中每个元素均为正整数。

我们定义旗帜的美观度为该矩阵中连通块（component）的数量。所谓连通块，是指一组具有相同数值的格子，且该组中任意两个格子之间均存在一条仅经过同值格子的相邻路径（上下左右四个方向）。下图展示了一个旗帜矩阵被划分成若干连通块的示例：

但这一次，他决定对计算过程稍作修改：他不再评估整面旗帜，而是只评估其中某个“段”（segment）。旗帜的一个段可描述为原旗帜矩阵的一个子矩阵，其对角顶点位于 $ (1,,l) $ 和 $ (n,,r) $，其中满足条件 $ 1 \leq l \leq r \leq m $。

请帮助弗拉基克计算给定旗帜的若干段的美观度。

First line contains three space-separated integers n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — dimensions of flag matrix and number of segments respectively.

Each of next n lines contains m space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 106.

Each of next q lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ m) — borders of segment which beauty Vladik wants to know.

第一行包含三个以空格分隔的整数 $n$、$m$、$q$（$1 \leq n \leq 10$，$1 \leq m,\,q \leq 10^5$）——分别为旗帜矩阵的维度及查询线段的数量。

接下来的 $n$ 行，每行包含 $m$ 个以空格分隔的整数——描述旗帜矩阵。旗帜矩阵的所有元素均为不超过 $10^6$ 的正整数。

接下来的 $q$ 行，每行包含两个以空格分隔的整数 $l$、$r$（$1 \leq l \leq r \leq m$）——表示弗拉迪克希望查询其“美观度”的线段边界。

For each segment print the result on the corresponding line.

对每个线段，在对应的行上输出结果。

Partitioning on components for every segment from first test case:

第一个测试用例中每个区间的连通分量划分：