1784 - Vladik and Entertaining Flags

1784.Vladik and Entertaining Flags

Time Limit: 1s Memory Limit: 256MB

In his spare time Vladik estimates beauty of the flags.Every flag could be represented as the matrix n \times 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: $1784_1.png$ 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 \le l \le r \le m are satisfied.Help Vladik to calculate the beauty for some segments of the given flag.

Input Format(From the terminal/stdin)

Input First line contains three space-separated integers n, m, q (1 \le n \le 10, 1 \le m,q \le 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 \le l \le r \le m)- borders of segment which beauty Vladik wants to know.

Output Format(To the terminal/stdout)

Output For each segment print the result on the corresponding line.

Sample Input

Copy

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
 · · \n
 · · · · \n
 · · · · \n
 · · · · \n
 · · · · \n
 · \n
 · \n
 · \n
 · \n

Sample Output

Copy

6
7
3
4
 \n
 \n
 \n
 \n

Hints

Partitioning on components for every segment from first test case: $1784_2.png$

Submit

请先登录

Submit

题解(0)