#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
T sqr(T a) {
  return a * a;
}
template <typename T>
int sign(T a) {
  if (a == 0) return 0;
  return (a > 0 ? 1 : -1);
}
template <typename T1, typename T2>
T2 sum_mod(T1 x, T2 MOD) {
  if (x < 0) x += MOD;
  if (x >= MOD) x -= MOD;
  return x;
}
template <typename T1, typename T2>
T2 mul_mod(T1 x, T2 MOD) {
  if (x < 0) return (abs(x) % MOD == 0 ? 0 : MOD - abs(x) % MOD);
  return x % MOD;
}
template <typename T>
bool uax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T& a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  out << p.first << ' ' << p.second;
  return out;
}
const int LOG = 18;
const int N = (int)2e5 + 7;
const int MAXN = (int)2e6 + 7;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9 + 7;
const int CONST = 300;
const long long LINF = (int64_t)2e15;
const long double PI = 3.1415926535897932384626433832795;
const long double EPS = 1;
struct Cell {
  int x, y, ind;
  Cell(){};
  Cell(int x, int y, int ind) : x(x), y(y), ind(ind){};
};
int maxc;
int n, m, q;
vector<int> add[MAXN];
int sz[N], par[N], ans[MAXN];
int f[307][307], cf[307][307];
vector<vector<Cell>> rep1, rep2;
int get_par(int u) {
  if (u == par[u]) return u;
  return par[u] = get_par(par[u]);
}
bool unite(int u, int v) {
  u = get_par(u), v = get_par(v);
  if (u == v) return false;
  if (sz[u] < sz[v]) swap(u, v);
  par[v] = u;
  sz[u] += sz[v];
  return true;
}
void build() {
  for (int i = 0; i < n * m; i++) par[i] = i, sz[i] = 1;
}
int get_num(int x, int y) { return x * m + y; }
int v[4] = {-1, 0, 0, 1}, h[4] = {0, -1, 1, 0};
int add_cell(int x, int y, int col) {
  int res = 0;
  for (int i = 0; i < 4; i++) {
    int nx = x + v[i], ny = y + h[i];
    if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
    if (cf[nx][ny] == col) res += unite(get_num(x, y), get_num(nx, ny));
  }
  cf[x][y] = col;
  return res;
}
int main() {
  double start = clock();
  cout << fixed << setprecision(20);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  maxc = max(1007, MAXN / (n * m) + 7);
  rep1.resize(maxc), rep2.resize(maxc);
  for (int i = 1; i <= q; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--;
    rep1[c].push_back(Cell(x, y, i));
    if (f[x][y] == c) continue;
    rep2[f[x][y]].push_back(Cell(x, y, i));
    f[x][y] = c;
  }
  for (int i = 0; i < maxc; i++) {
    build();
    for (int j = 0; j < n; j++) fill(cf[j], cf[j] + m, -1);
    int comp = 0;
    for (auto it : rep1[i]) {
      int x = it.x, y = it.y, ind = it.ind;
      if (cf[x][y] == -1) {
        comp++;
        comp -= add_cell(x, y, i);
      }
      ans[ind] += comp;
    }
    if ((int)rep1[i].size() != 0) {
      int l = rep1[i].back().ind + 1,
          r = ((int)rep2[i].size() == 0 ? q : rep2[i][0].ind - 1);
      if (l <= r) {
        add[l].push_back(comp);
        add[r].push_back(-comp);
      }
    }
    build();
    if (i == 0) {
      for (int j = 0; j < n; j++) fill(cf[j], cf[j] + m, 0);
    }
    for (auto it : rep2[i]) {
      int x = it.x, y = it.y;
      cf[x][y] = -1;
    }
    comp = 0;
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        if (cf[j][k] == -1) continue;
        comp++;
        comp -= add_cell(j, k, i);
      }
    }
    int lst = q + 1;
    for (int j = (int)rep2[i].size() - 1; j >= 0; j--) {
      int x = rep2[i][j].x, y = rep2[i][j].y, ind = rep2[i][j].ind;
      add[ind].push_back(comp);
      add[lst - 1].push_back(-comp);
      if (cf[x][y] == -1) {
        comp++;
        comp -= add_cell(x, y, i);
      }
      lst = ind;
    }
  }
  int cnt = 0;
  for (int i = 0; i < MAXN; i++) {
    sort(add[i].begin(), add[i].end());
    while ((int)add[i].size() > 0 && add[i].back() > 0) {
      cnt += add[i].back();
      add[i].pop_back();
    }
    ans[i] += cnt;
    while ((int)add[i].size() > 0) {
      cnt += add[i].back();
      add[i].pop_back();
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

### Prompt

In Cpp, your task is to solve 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>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
T sqr(T a) {
  return a * a;
}
template <typename T>
int sign(T a) {
  if (a == 0) return 0;
  return (a > 0 ? 1 : -1);
}
template <typename T1, typename T2>
T2 sum_mod(T1 x, T2 MOD) {
  if (x < 0) x += MOD;
  if (x >= MOD) x -= MOD;
  return x;
}
template <typename T1, typename T2>
T2 mul_mod(T1 x, T2 MOD) {
  if (x < 0) return (abs(x) % MOD == 0 ? 0 : MOD - abs(x) % MOD);
  return x % MOD;
}
template <typename T>
bool uax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T& a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  out << p.first << ' ' << p.second;
  return out;
}
const int LOG = 18;
const int N = (int)2e5 + 7;
const int MAXN = (int)2e6 + 7;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9 + 7;
const int CONST = 300;
const long long LINF = (int64_t)2e15;
const long double PI = 3.1415926535897932384626433832795;
const long double EPS = 1;
struct Cell {
  int x, y, ind;
  Cell(){};
  Cell(int x, int y, int ind) : x(x), y(y), ind(ind){};
};
int maxc;
int n, m, q;
vector<int> add[MAXN];
int sz[N], par[N], ans[MAXN];
int f[307][307], cf[307][307];
vector<vector<Cell>> rep1, rep2;
int get_par(int u) {
  if (u == par[u]) return u;
  return par[u] = get_par(par[u]);
}
bool unite(int u, int v) {
  u = get_par(u), v = get_par(v);
  if (u == v) return false;
  if (sz[u] < sz[v]) swap(u, v);
  par[v] = u;
  sz[u] += sz[v];
  return true;
}
void build() {
  for (int i = 0; i < n * m; i++) par[i] = i, sz[i] = 1;
}
int get_num(int x, int y) { return x * m + y; }
int v[4] = {-1, 0, 0, 1}, h[4] = {0, -1, 1, 0};
int add_cell(int x, int y, int col) {
  int res = 0;
  for (int i = 0; i < 4; i++) {
    int nx = x + v[i], ny = y + h[i];
    if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
    if (cf[nx][ny] == col) res += unite(get_num(x, y), get_num(nx, ny));
  }
  cf[x][y] = col;
  return res;
}
int main() {
  double start = clock();
  cout << fixed << setprecision(20);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  maxc = max(1007, MAXN / (n * m) + 7);
  rep1.resize(maxc), rep2.resize(maxc);
  for (int i = 1; i <= q; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--;
    rep1[c].push_back(Cell(x, y, i));
    if (f[x][y] == c) continue;
    rep2[f[x][y]].push_back(Cell(x, y, i));
    f[x][y] = c;
  }
  for (int i = 0; i < maxc; i++) {
    build();
    for (int j = 0; j < n; j++) fill(cf[j], cf[j] + m, -1);
    int comp = 0;
    for (auto it : rep1[i]) {
      int x = it.x, y = it.y, ind = it.ind;
      if (cf[x][y] == -1) {
        comp++;
        comp -= add_cell(x, y, i);
      }
      ans[ind] += comp;
    }
    if ((int)rep1[i].size() != 0) {
      int l = rep1[i].back().ind + 1,
          r = ((int)rep2[i].size() == 0 ? q : rep2[i][0].ind - 1);
      if (l <= r) {
        add[l].push_back(comp);
        add[r].push_back(-comp);
      }
    }
    build();
    if (i == 0) {
      for (int j = 0; j < n; j++) fill(cf[j], cf[j] + m, 0);
    }
    for (auto it : rep2[i]) {
      int x = it.x, y = it.y;
      cf[x][y] = -1;
    }
    comp = 0;
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        if (cf[j][k] == -1) continue;
        comp++;
        comp -= add_cell(j, k, i);
      }
    }
    int lst = q + 1;
    for (int j = (int)rep2[i].size() - 1; j >= 0; j--) {
      int x = rep2[i][j].x, y = rep2[i][j].y, ind = rep2[i][j].ind;
      add[ind].push_back(comp);
      add[lst - 1].push_back(-comp);
      if (cf[x][y] == -1) {
        comp++;
        comp -= add_cell(x, y, i);
      }
      lst = ind;
    }
  }
  int cnt = 0;
  for (int i = 0; i < MAXN; i++) {
    sort(add[i].begin(), add[i].end());
    while ((int)add[i].size() > 0 && add[i].back() > 0) {
      cnt += add[i].back();
      add[i].pop_back();
    }
    ans[i] += cnt;
    while ((int)add[i].size() > 0) {
      cnt += add[i].back();
      add[i].pop_back();
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

```