#include <bits/stdc++.h>
using namespace std;
const int MaxN = 11, MaxM = 100003, MaxQ = 100003;
int n, m, q;
int c[MaxN][MaxM];
struct node {
  int blocks;
  int l[MaxN], r[MaxN];
} s[MaxM << 2];
inline void uni(int* fa, int a, int b, int limit) {
  for (int i = 1; i <= limit; i++)
    if (fa[i] == b) fa[i] = a;
}
int uni2(int* ll, const int* lr, const int* rl, int* rr, const int& rowl,
         const int& rowr) {
  static int a[100], b[100];
  memset(a, 0, sizeof a);
  int midl = (rowl + rowr) / 2, midr = midl + 1;
  int sum = 0, sum2 = 0;
  for (int i = 1; i <= n; i++)
    a[i] = ll[i], a[i + n] = lr[i], a[i + 2 * n] = rl[i], a[i + 3 * n] = rr[i];
  for (int i = 1; i <= 4 * n; i++) b[i] = a[i];
  sort(b + 1, b + 4 * n + 1);
  for (int i = 2; i <= 4 * n; i++)
    if (b[i] != b[i - 1]) sum++;
  for (int i = 1; i <= n; i++)
    if (c[i][midl] == c[i][midr]) uni(a, a[i + n], a[i + 2 * n], 4 * n);
  for (int i = 1; i <= 4 * n; i++) b[i] = a[i];
  sort(b + 1, b + 4 * n + 1);
  for (int i = 2; i <= 4 * n; i++)
    if (b[i] != b[i - 1]) sum2++;
  for (int i = 1; i <= n; i++) ll[i] = a[i];
  for (int i = 1; i <= n; i++) rr[i] = a[i + 3 * n];
  return sum - sum2;
}
void build(int p, int l, int r) {
  if (l == r) {
    s[p].blocks = n;
    for (int i = 1; i <= n; i++) s[p].l[i] = s[p].r[i] = n * (l - 1) + i;
    for (int i = 1; i < n; i++)
      if (c[i][l] == c[i + 1][l])
        uni(s[p].l, s[p].l[i], s[p].l[i + 1], n),
            uni(s[p].r, s[p].r[i], s[p].r[i + 1], n), s[p].blocks--;
    return;
  }
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  s[p].blocks = s[p * 2].blocks + s[p * 2 + 1].blocks;
  for (int i = 1; i <= n; i++)
    s[p].l[i] = s[p * 2].l[i], s[p].r[i] = s[p * 2 + 1].r[i];
  s[p].blocks -= uni2(s[p].l, s[p * 2].r, s[p * 2 + 1].l, s[p].r, l, r);
}
node query(int p, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) return s[p];
  int mid = (l + r) / 2;
  node left, right;
  bool fl = false, fr = false;
  if (ll <= mid) left = query(p * 2, l, mid, ll, rr), fl = true;
  if (rr > mid) right = query(p * 2 + 1, mid + 1, r, ll, rr), fr = true;
  if (fl && !fr) return left;
  if (!fl && fr) return right;
  node ret;
  ret.blocks = left.blocks + right.blocks;
  for (int i = 1; i <= n; i++) ret.l[i] = left.l[i], ret.r[i] = right.r[i];
  ret.blocks -= uni2(ret.l, left.r, right.l, ret.r, mid, mid + 1);
  return ret;
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      scanf("%d", &(c[i][j]));
    }
  build(1, 1, m);
  node t;
  int l, r;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &l, &r);
    t = query(1, 1, m, l, r);
    printf("%d\n", t.blocks);
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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:

<image>

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.

Input

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.

Output

For each segment print the result on the corresponding line.

Example

Input

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


Output

6
7
3
4

Note

Partitioning on components for every segment from first test case:

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 11, MaxM = 100003, MaxQ = 100003;
int n, m, q;
int c[MaxN][MaxM];
struct node {
  int blocks;
  int l[MaxN], r[MaxN];
} s[MaxM << 2];
inline void uni(int* fa, int a, int b, int limit) {
  for (int i = 1; i <= limit; i++)
    if (fa[i] == b) fa[i] = a;
}
int uni2(int* ll, const int* lr, const int* rl, int* rr, const int& rowl,
         const int& rowr) {
  static int a[100], b[100];
  memset(a, 0, sizeof a);
  int midl = (rowl + rowr) / 2, midr = midl + 1;
  int sum = 0, sum2 = 0;
  for (int i = 1; i <= n; i++)
    a[i] = ll[i], a[i + n] = lr[i], a[i + 2 * n] = rl[i], a[i + 3 * n] = rr[i];
  for (int i = 1; i <= 4 * n; i++) b[i] = a[i];
  sort(b + 1, b + 4 * n + 1);
  for (int i = 2; i <= 4 * n; i++)
    if (b[i] != b[i - 1]) sum++;
  for (int i = 1; i <= n; i++)
    if (c[i][midl] == c[i][midr]) uni(a, a[i + n], a[i + 2 * n], 4 * n);
  for (int i = 1; i <= 4 * n; i++) b[i] = a[i];
  sort(b + 1, b + 4 * n + 1);
  for (int i = 2; i <= 4 * n; i++)
    if (b[i] != b[i - 1]) sum2++;
  for (int i = 1; i <= n; i++) ll[i] = a[i];
  for (int i = 1; i <= n; i++) rr[i] = a[i + 3 * n];
  return sum - sum2;
}
void build(int p, int l, int r) {
  if (l == r) {
    s[p].blocks = n;
    for (int i = 1; i <= n; i++) s[p].l[i] = s[p].r[i] = n * (l - 1) + i;
    for (int i = 1; i < n; i++)
      if (c[i][l] == c[i + 1][l])
        uni(s[p].l, s[p].l[i], s[p].l[i + 1], n),
            uni(s[p].r, s[p].r[i], s[p].r[i + 1], n), s[p].blocks--;
    return;
  }
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  s[p].blocks = s[p * 2].blocks + s[p * 2 + 1].blocks;
  for (int i = 1; i <= n; i++)
    s[p].l[i] = s[p * 2].l[i], s[p].r[i] = s[p * 2 + 1].r[i];
  s[p].blocks -= uni2(s[p].l, s[p * 2].r, s[p * 2 + 1].l, s[p].r, l, r);
}
node query(int p, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) return s[p];
  int mid = (l + r) / 2;
  node left, right;
  bool fl = false, fr = false;
  if (ll <= mid) left = query(p * 2, l, mid, ll, rr), fl = true;
  if (rr > mid) right = query(p * 2 + 1, mid + 1, r, ll, rr), fr = true;
  if (fl && !fr) return left;
  if (!fl && fr) return right;
  node ret;
  ret.blocks = left.blocks + right.blocks;
  for (int i = 1; i <= n; i++) ret.l[i] = left.l[i], ret.r[i] = right.r[i];
  ret.blocks -= uni2(ret.l, left.r, right.l, ret.r, mid, mid + 1);
  return ret;
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      scanf("%d", &(c[i][j]));
    }
  build(1, 1, m);
  node t;
  int l, r;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &l, &r);
    t = query(1, 1, m, l, r);
    printf("%d\n", t.blocks);
  }
  return 0;
}

```