#include <bits/stdc++.h>
using namespace std;
const long long INFL = 1LL << 60;
const long long INF = 1 << 30;
long long MOD = 1000000007;
vector<long long> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<long long> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};
void pres(double A) { printf("%.9lf\n", A); }
void BinarySay(long long x, long long y = 60) {
  for (int i = 0; i < (y); i++) cout << (x >> (y - 1 - i) & 1);
  cout << endl;
}
long long cnt_bit(long long x) { return __builtin_popcountll(x); }
long long pow_long(long long x, long long k) {
  long long res = 1;
  while (k > 0) {
    if (k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
long long pow_mod(long long x, long long k) {
  long long res = 1;
  while (k > 0) {
    if (k % 2) {
      res *= x;
      res %= MOD;
    }
    x *= x;
    x %= MOD;
    k /= 2;
  }
  return res;
}
long long inverse(long long x) { return pow_mod(x, MOD - 2); };
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long x, long long y) {
  long long res = x / gcd(x, y);
  res *= y;
  return res;
};
const int MAXcomb = 2000010;
long long fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAXcomb; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
long long comb(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * finv[k] % MOD * finv[n - k] % MOD;
}
const int MAXkai = 200010;
long long kai_memo[MAXkai];
long long kai(long long N) {
  if (kai_memo[N] != 0) return kai_memo[N];
  if (N <= 1) return 1;
  return kai_memo[N] = N * kai(N - 1) % MOD;
}
long long disit(long long second, long long base = 10) {
  long long res = 0;
  while (second) {
    res++;
    second /= base;
  }
  return res;
}
vector<long long> divisor(long long n) {
  vector<long long> res(0);
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
  sort(res.begin(), res.end());
  return res;
}
const int MAX_V = 1000010;
int par[MAX_V];
int Rank[MAX_V];
void init_UF(int X) {
  for (int i = 0; i < X; i++) {
    par[i] = i;
    Rank[i] = 1;
  }
}
int find(int x) {
  if (par[x] == x)
    return x;
  else {
    return par[x] = find(par[x]);
  }
}
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) {
  int rx = find(x), ry = find(y);
  if (rx != ry) {
    if (Rank[rx] >= Rank[ry]) {
      par[ry] = rx;
      if (Rank[rx] == Rank[ry]) Rank[rx]++;
    } else {
      par[rx] = ry;
    }
  }
}
int N, M, Q;
vector<pair<int, int>> query[2000010];
int mp[310][310];
void solve() {
  cin >> N >> M >> Q;
  for (int i = 0; i < (Q); i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--;
    query[c].push_back({x, y});
  }
  vector<int> change(Q);
  vector<int> ans(Q);
  int id = 0;
  for (int i = 0; i < (2000010); i++)
    if (query[i].size()) {
      init_UF(N * M);
      int add = 0;
      for (pair<int, int> p : query[i]) {
        if (mp[p.first][p.second] != i) add++;
        if (p.first - 1 >= 0 && mp[p.first - 1][p.second] == i) {
          if (!same(M * (p.first - 1) + p.second, M * p.first + p.second))
            add--;
          unite(M * (p.first - 1) + p.second, M * p.first + p.second);
        }
        if (p.first + 1 < N && mp[p.first + 1][p.second] == i) {
          if (!same(M * (p.first + 1) + p.second, M * p.first + p.second))
            add--;
          unite(M * (p.first + 1) + p.second, M * p.first + p.second);
        }
        if (p.second - 1 >= 0 && mp[p.first][p.second - 1] == i) {
          if (!same(M * p.first + p.second - 1, M * p.first + p.second)) add--;
          unite(M * p.first + p.second - 1, M * p.first + p.second);
        }
        if (p.second + 1 < M && mp[p.first][p.second + 1] == i) {
          if (!same(M * p.first + p.second + 1, M * p.first + p.second)) add--;
          unite(M * p.first + p.second + 1, M * p.first + p.second);
        }
        change[id] = mp[p.first][p.second];
        mp[p.first][p.second] = i;
        ans[id] = add;
        id++;
      }
    }
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (M); j++) {
      if (i - 1 >= 0 && mp[i - 1][j] == mp[i][j])
        unite((i - 1) * M + j, i * M + j);
      if (i + 1 < N && mp[i + 1][j] == mp[i][j])
        unite((i + 1) * M + j, i * M + j);
      if (j - 1 >= 0 && mp[i][j - 1] == mp[i][j])
        unite(i * M + j - 1, i * M + j);
      if (j + 1 < M && mp[i][j + 1] == mp[i][j])
        unite(i * M + j + 1, i * M + j);
    }
  int sum = 0;
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (M); j++)
      if (find(i * M + j) == i * M + j) sum++;
  id = Q - 1;
  for (long long i = (2000010) - 1; i >= 0; i--)
    if (query[i].size()) {
      init_UF(N * M);
      for (int j = 0; j < (N); j++)
        for (int k = 0; k < (M); k++)
          if (mp[j][k] != i) {
            if (j - 1 >= 0 && mp[j - 1][k] == mp[j][k])
              unite((j - 1) * M + k, j * M + k);
            if (j + 1 < N && mp[j + 1][k] == mp[j][k])
              unite((j + 1) * M + k, j * M + k);
            if (k - 1 >= 0 && mp[j][k - 1] == mp[j][k])
              unite(j * M + k - 1, j * M + k);
            if (k + 1 < M && mp[j][k + 1] == mp[j][k])
              unite(j * M + k + 1, j * M + k);
          }
      sum = 0;
      for (int j = 0; j < (N); j++)
        for (int k = 0; k < (M); k++)
          if (mp[j][k] != i)
            if (find(j * M + k) == j * M + k) sum++;
      for (int j = query[i].size() - 1; j >= 0; j--) {
        ans[id] += sum;
        pair<int, int> p = query[i][j];
        if (mp[p.first][p.second] != change[id]) {
          mp[p.first][p.second] = change[id];
          sum++;
          if (p.first - 1 >= 0 &&
              mp[p.first - 1][p.second] == mp[p.first][p.second]) {
            if (!same(M * (p.first - 1) + p.second, M * p.first + p.second))
              sum--;
            unite(M * (p.first - 1) + p.second, M * p.first + p.second);
          }
          if (p.first + 1 < N &&
              mp[p.first + 1][p.second] == mp[p.first][p.second]) {
            if (!same(M * (p.first + 1) + p.second, M * p.first + p.second))
              sum--;
            unite(M * (p.first + 1) + p.second, M * p.first + p.second);
          }
          if (p.second - 1 >= 0 &&
              mp[p.first][p.second - 1] == mp[p.first][p.second]) {
            if (!same(M * p.first + p.second - 1, M * p.first + p.second))
              sum--;
            unite(M * p.first + p.second - 1, M * p.first + p.second);
          }
          if (p.second + 1 < M &&
              mp[p.first][p.second + 1] == mp[p.first][p.second]) {
            if (!same(M * p.first + p.second + 1, M * p.first + p.second))
              sum--;
            unite(M * p.first + p.second + 1, M * p.first + p.second);
          }
        }
        id--;
      }
    }
  for (int i = 0; i < (Q); i++) {
    printf("%d\n", ans[i]);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}

### Prompt

Your task is to create a Cpp solution to the following problem:

You are given a matrix n × m, initially filled with zeroes. We define a_{i, j} as the element in the i-th row and the j-th column of the matrix.

Two cells of the matrix are connected if they share a side, and the elements in these cells are equal. Two cells of the matrix belong to the same connected component if there exists a sequence s_1, s_2, ..., s_k such that s_1 is the first cell, s_k is the second cell, and for every i ∈ [1, k - 1], s_i and s_{i + 1} are connected.

You are given q queries of the form x_i y_i c_i (i ∈ [1, q]). For every such query, you have to do the following:

  1. replace the element a_{x, y} with c; 
  2. count the number of connected components in the matrix. 



There is one additional constraint: for every i ∈ [1, q - 1], c_i ≤ c_{i + 1}.

Input

The first line contains three integers n, m and q (1 ≤ n, m ≤ 300, 1 ≤ q ≤ 2 ⋅ 10^6) — the number of rows, the number of columns and the number of queries, respectively.

Then q lines follow, each representing a query. The i-th line contains three integers x_i, y_i and c_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ c_i ≤ max(1000, ⌈ (2 ⋅ 10^6)/(nm) ⌉)). For every i ∈ [1, q - 1], c_i ≤ c_{i + 1}.

Output

Print q integers, the i-th of them should be equal to the number of components in the matrix after the first i queries are performed.

Example

Input


3 2 10
2 1 1
1 2 1
2 2 1
1 1 2
3 1 2
1 2 2
2 2 2
2 1 2
3 2 4
2 1 5


Output


2
4
3
3
4
4
4
2
2
4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long INFL = 1LL << 60;
const long long INF = 1 << 30;
long long MOD = 1000000007;
vector<long long> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<long long> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};
void pres(double A) { printf("%.9lf\n", A); }
void BinarySay(long long x, long long y = 60) {
  for (int i = 0; i < (y); i++) cout << (x >> (y - 1 - i) & 1);
  cout << endl;
}
long long cnt_bit(long long x) { return __builtin_popcountll(x); }
long long pow_long(long long x, long long k) {
  long long res = 1;
  while (k > 0) {
    if (k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
long long pow_mod(long long x, long long k) {
  long long res = 1;
  while (k > 0) {
    if (k % 2) {
      res *= x;
      res %= MOD;
    }
    x *= x;
    x %= MOD;
    k /= 2;
  }
  return res;
}
long long inverse(long long x) { return pow_mod(x, MOD - 2); };
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long x, long long y) {
  long long res = x / gcd(x, y);
  res *= y;
  return res;
};
const int MAXcomb = 2000010;
long long fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAXcomb; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
long long comb(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * finv[k] % MOD * finv[n - k] % MOD;
}
const int MAXkai = 200010;
long long kai_memo[MAXkai];
long long kai(long long N) {
  if (kai_memo[N] != 0) return kai_memo[N];
  if (N <= 1) return 1;
  return kai_memo[N] = N * kai(N - 1) % MOD;
}
long long disit(long long second, long long base = 10) {
  long long res = 0;
  while (second) {
    res++;
    second /= base;
  }
  return res;
}
vector<long long> divisor(long long n) {
  vector<long long> res(0);
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
  sort(res.begin(), res.end());
  return res;
}
const int MAX_V = 1000010;
int par[MAX_V];
int Rank[MAX_V];
void init_UF(int X) {
  for (int i = 0; i < X; i++) {
    par[i] = i;
    Rank[i] = 1;
  }
}
int find(int x) {
  if (par[x] == x)
    return x;
  else {
    return par[x] = find(par[x]);
  }
}
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) {
  int rx = find(x), ry = find(y);
  if (rx != ry) {
    if (Rank[rx] >= Rank[ry]) {
      par[ry] = rx;
      if (Rank[rx] == Rank[ry]) Rank[rx]++;
    } else {
      par[rx] = ry;
    }
  }
}
int N, M, Q;
vector<pair<int, int>> query[2000010];
int mp[310][310];
void solve() {
  cin >> N >> M >> Q;
  for (int i = 0; i < (Q); i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--;
    query[c].push_back({x, y});
  }
  vector<int> change(Q);
  vector<int> ans(Q);
  int id = 0;
  for (int i = 0; i < (2000010); i++)
    if (query[i].size()) {
      init_UF(N * M);
      int add = 0;
      for (pair<int, int> p : query[i]) {
        if (mp[p.first][p.second] != i) add++;
        if (p.first - 1 >= 0 && mp[p.first - 1][p.second] == i) {
          if (!same(M * (p.first - 1) + p.second, M * p.first + p.second))
            add--;
          unite(M * (p.first - 1) + p.second, M * p.first + p.second);
        }
        if (p.first + 1 < N && mp[p.first + 1][p.second] == i) {
          if (!same(M * (p.first + 1) + p.second, M * p.first + p.second))
            add--;
          unite(M * (p.first + 1) + p.second, M * p.first + p.second);
        }
        if (p.second - 1 >= 0 && mp[p.first][p.second - 1] == i) {
          if (!same(M * p.first + p.second - 1, M * p.first + p.second)) add--;
          unite(M * p.first + p.second - 1, M * p.first + p.second);
        }
        if (p.second + 1 < M && mp[p.first][p.second + 1] == i) {
          if (!same(M * p.first + p.second + 1, M * p.first + p.second)) add--;
          unite(M * p.first + p.second + 1, M * p.first + p.second);
        }
        change[id] = mp[p.first][p.second];
        mp[p.first][p.second] = i;
        ans[id] = add;
        id++;
      }
    }
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (M); j++) {
      if (i - 1 >= 0 && mp[i - 1][j] == mp[i][j])
        unite((i - 1) * M + j, i * M + j);
      if (i + 1 < N && mp[i + 1][j] == mp[i][j])
        unite((i + 1) * M + j, i * M + j);
      if (j - 1 >= 0 && mp[i][j - 1] == mp[i][j])
        unite(i * M + j - 1, i * M + j);
      if (j + 1 < M && mp[i][j + 1] == mp[i][j])
        unite(i * M + j + 1, i * M + j);
    }
  int sum = 0;
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (M); j++)
      if (find(i * M + j) == i * M + j) sum++;
  id = Q - 1;
  for (long long i = (2000010) - 1; i >= 0; i--)
    if (query[i].size()) {
      init_UF(N * M);
      for (int j = 0; j < (N); j++)
        for (int k = 0; k < (M); k++)
          if (mp[j][k] != i) {
            if (j - 1 >= 0 && mp[j - 1][k] == mp[j][k])
              unite((j - 1) * M + k, j * M + k);
            if (j + 1 < N && mp[j + 1][k] == mp[j][k])
              unite((j + 1) * M + k, j * M + k);
            if (k - 1 >= 0 && mp[j][k - 1] == mp[j][k])
              unite(j * M + k - 1, j * M + k);
            if (k + 1 < M && mp[j][k + 1] == mp[j][k])
              unite(j * M + k + 1, j * M + k);
          }
      sum = 0;
      for (int j = 0; j < (N); j++)
        for (int k = 0; k < (M); k++)
          if (mp[j][k] != i)
            if (find(j * M + k) == j * M + k) sum++;
      for (int j = query[i].size() - 1; j >= 0; j--) {
        ans[id] += sum;
        pair<int, int> p = query[i][j];
        if (mp[p.first][p.second] != change[id]) {
          mp[p.first][p.second] = change[id];
          sum++;
          if (p.first - 1 >= 0 &&
              mp[p.first - 1][p.second] == mp[p.first][p.second]) {
            if (!same(M * (p.first - 1) + p.second, M * p.first + p.second))
              sum--;
            unite(M * (p.first - 1) + p.second, M * p.first + p.second);
          }
          if (p.first + 1 < N &&
              mp[p.first + 1][p.second] == mp[p.first][p.second]) {
            if (!same(M * (p.first + 1) + p.second, M * p.first + p.second))
              sum--;
            unite(M * (p.first + 1) + p.second, M * p.first + p.second);
          }
          if (p.second - 1 >= 0 &&
              mp[p.first][p.second - 1] == mp[p.first][p.second]) {
            if (!same(M * p.first + p.second - 1, M * p.first + p.second))
              sum--;
            unite(M * p.first + p.second - 1, M * p.first + p.second);
          }
          if (p.second + 1 < M &&
              mp[p.first][p.second + 1] == mp[p.first][p.second]) {
            if (!same(M * p.first + p.second + 1, M * p.first + p.second))
              sum--;
            unite(M * p.first + p.second + 1, M * p.first + p.second);
          }
        }
        id--;
      }
    }
  for (int i = 0; i < (Q); i++) {
    printf("%d\n", ans[i]);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}

```