#include <bits/stdc++.h>
using namespace std;
int Map[10][100005];
int sum[4 * 100005];
pair<int, int> Fnd[19][10][100005];
pair<int, int> Tmp[10][100005];
int n, m;
pair<int, int> Find(pair<int, int> F[][100005], pair<int, int> x) {
  if (F[x.first][x.second] == x) return x;
  return F[x.first][x.second] = Find(F, F[x.first][x.second]);
}
pair<int, int> Copy(pair<int, int> F[][100005], pair<int, int> FF[][100005],
                    pair<int, int> x) {
  if (FF[x.first][x.second] == x)
    return F[x.first][x.second] = FF[x.first][x.second] = x;
  return F[x.first][x.second] = FF[x.first][x.second] =
             Copy(F, FF, FF[x.first][x.second]);
}
int work(int st, int pos, int depth) {
  int i;
  int sm = n;
  for (i = 0; i < n; i++) {
    Fnd[depth][i][st] = make_pair(i, st);
  }
  for (i = 1; i < n; i++) {
    if (Map[i][st] == Map[i - 1][st]) {
      Fnd[depth][i][st] = Fnd[depth][i - 1][st];
      sm--;
    }
  }
  return sm;
}
void build(int l, int r, int pos, int depth) {
  if (l == r) {
    sum[pos] = work(l, pos, depth);
    return;
  }
  int mid = (l + r) >> 1;
  int i;
  build(l, mid, pos << 1, depth + 1);
  build(mid + 1, r, pos << 1 | 1, depth + 1);
  sum[pos] = sum[pos << 1] + sum[pos << 1 | 1];
  for (i = 0; i < n; i++) {
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, l});
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, mid});
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, mid + 1});
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, r});
  }
  for (i = 0; i < n; i++) {
    if (Map[i][mid] == Map[i][mid + 1]) {
      pair<int, int> n1 = Find(Fnd[depth], Fnd[depth][i][mid]);
      pair<int, int> n2 = Find(Fnd[depth], Fnd[depth][i][mid + 1]);
      if (n1 == n2) continue;
      sum[pos]--;
      Fnd[depth][n1.first][n1.second] = n2;
    }
  }
}
void qury(int l, int r, int pos, int depth, int l1, int r1, int &ans) {
  int i;
  if (l1 <= l && r1 >= r) {
    ans += sum[pos];
    for (i = 0; i < n; i++) {
      Copy(Tmp, Fnd[depth], (pair<int, int>){i, l});
      Copy(Tmp, Fnd[depth], (pair<int, int>){i, r});
    }
    return;
  }
  int mid = (l + r) >> 1;
  int s0 = 0;
  if (mid >= l1) {
    qury(l, mid, pos << 1, depth + 1, l1, r1, ans);
    s0 = 1;
  }
  if (mid + 1 <= r1) {
    qury(mid + 1, r, pos << 1 | 1, depth + 1, l1, r1, ans);
    if (!s0) return;
    for (i = 0; i < n; i++) {
      if (Map[i][mid + 1] == Map[i][mid]) {
        pair<int, int> n1 = Find(Tmp, Tmp[i][mid]);
        pair<int, int> n2 = Find(Tmp, Tmp[i][mid + 1]);
        if (n1 == n2) continue;
        ans--;
        Tmp[n1.first][n1.second] = n2;
      }
    }
  }
}
int main() {
  int i, j, k;
  int l, r, q;
  scanf("%d%d%d", &n, &m, &q);
  for (i = 0; i < n; i++) {
    for (j = 1; j <= m; j++) {
      scanf("%d", &Map[i][j]);
    }
  }
  build(1, m, 1, 0);
  for (i = 0; i < q; i++) {
    int ans = 0;
    scanf("%d%d", &l, &r);
    qury(1, m, 1, 0, l, r, ans);
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
int Map[10][100005];
int sum[4 * 100005];
pair<int, int> Fnd[19][10][100005];
pair<int, int> Tmp[10][100005];
int n, m;
pair<int, int> Find(pair<int, int> F[][100005], pair<int, int> x) {
  if (F[x.first][x.second] == x) return x;
  return F[x.first][x.second] = Find(F, F[x.first][x.second]);
}
pair<int, int> Copy(pair<int, int> F[][100005], pair<int, int> FF[][100005],
                    pair<int, int> x) {
  if (FF[x.first][x.second] == x)
    return F[x.first][x.second] = FF[x.first][x.second] = x;
  return F[x.first][x.second] = FF[x.first][x.second] =
             Copy(F, FF, FF[x.first][x.second]);
}
int work(int st, int pos, int depth) {
  int i;
  int sm = n;
  for (i = 0; i < n; i++) {
    Fnd[depth][i][st] = make_pair(i, st);
  }
  for (i = 1; i < n; i++) {
    if (Map[i][st] == Map[i - 1][st]) {
      Fnd[depth][i][st] = Fnd[depth][i - 1][st];
      sm--;
    }
  }
  return sm;
}
void build(int l, int r, int pos, int depth) {
  if (l == r) {
    sum[pos] = work(l, pos, depth);
    return;
  }
  int mid = (l + r) >> 1;
  int i;
  build(l, mid, pos << 1, depth + 1);
  build(mid + 1, r, pos << 1 | 1, depth + 1);
  sum[pos] = sum[pos << 1] + sum[pos << 1 | 1];
  for (i = 0; i < n; i++) {
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, l});
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, mid});
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, mid + 1});
    Copy(Fnd[depth], Fnd[depth + 1], pair<int, int>{i, r});
  }
  for (i = 0; i < n; i++) {
    if (Map[i][mid] == Map[i][mid + 1]) {
      pair<int, int> n1 = Find(Fnd[depth], Fnd[depth][i][mid]);
      pair<int, int> n2 = Find(Fnd[depth], Fnd[depth][i][mid + 1]);
      if (n1 == n2) continue;
      sum[pos]--;
      Fnd[depth][n1.first][n1.second] = n2;
    }
  }
}
void qury(int l, int r, int pos, int depth, int l1, int r1, int &ans) {
  int i;
  if (l1 <= l && r1 >= r) {
    ans += sum[pos];
    for (i = 0; i < n; i++) {
      Copy(Tmp, Fnd[depth], (pair<int, int>){i, l});
      Copy(Tmp, Fnd[depth], (pair<int, int>){i, r});
    }
    return;
  }
  int mid = (l + r) >> 1;
  int s0 = 0;
  if (mid >= l1) {
    qury(l, mid, pos << 1, depth + 1, l1, r1, ans);
    s0 = 1;
  }
  if (mid + 1 <= r1) {
    qury(mid + 1, r, pos << 1 | 1, depth + 1, l1, r1, ans);
    if (!s0) return;
    for (i = 0; i < n; i++) {
      if (Map[i][mid + 1] == Map[i][mid]) {
        pair<int, int> n1 = Find(Tmp, Tmp[i][mid]);
        pair<int, int> n2 = Find(Tmp, Tmp[i][mid + 1]);
        if (n1 == n2) continue;
        ans--;
        Tmp[n1.first][n1.second] = n2;
      }
    }
  }
}
int main() {
  int i, j, k;
  int l, r, q;
  scanf("%d%d%d", &n, &m, &q);
  for (i = 0; i < n; i++) {
    for (j = 1; j <= m; j++) {
      scanf("%d", &Map[i][j]);
    }
  }
  build(1, m, 1, 0);
  for (i = 0; i < q; i++) {
    int ans = 0;
    scanf("%d%d", &l, &r);
    qury(1, m, 1, 0, l, r, ans);
    printf("%d\n", ans);
  }
  return 0;
}

```