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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
const int SIZE = 1 << 16;
char buf[SIZE], obuf[SIZE], str[60];
int bi = SIZE, bn = SIZE, opt;
double D[] = {0.1,      0.01,      0.001,      0.0001,      0.00001,
              0.000001, 0.0000001, 0.00000001, 0.000000001, 0.0000000001};
int read(char* s) {
  while (bn) {
    for (; bi < bn && buf[bi] <= ' '; bi++)
      ;
    if (bi < bn) break;
    bn = fread(buf, 1, SIZE, stdin);
    bi = 0;
  }
  int sn = 0;
  while (bn) {
    for (; bi < bn && buf[bi] > ' '; bi++) s[sn++] = buf[bi];
    if (bi < bn) break;
    bn = fread(buf, 1, SIZE, stdin);
    bi = 0;
  }
  s[sn] = 0;
  return sn;
}
bool read(int& x) {
  int n = read(str), bf = 0;
  if (!n) return 0;
  int i = 0;
  if (str[i] == '-')
    bf = 1, i++;
  else if (str[i] == '+')
    i++;
  for (x = 0; i < n; i++) x = x * 10 + str[i] - '0';
  if (bf) x = -x;
  return 1;
}
bool read(long long& x) {
  int n = read(str), bf;
  if (!n) return 0;
  int i = 0;
  if (str[i] == '-')
    bf = -1, i++;
  else
    bf = 1;
  for (x = 0; i < n; i++) x = x * 10 + str[i] - '0';
  if (bf < 0) x = -x;
  return 1;
}
void write(int x) {
  if (x == 0)
    obuf[opt++] = '0';
  else {
    if (x < 0) obuf[opt++] = '-', x = -x;
    int sn = 0;
    while (x) str[sn++] = x % 10 + '0', x /= 10;
    for (int i = sn - 1; i >= 0; i--) obuf[opt++] = str[i];
  }
  if (opt >= (SIZE >> 1)) {
    fwrite(obuf, 1, opt, stdout);
    opt = 0;
  }
}
void write(long long x) {
  if (x == 0)
    obuf[opt++] = '0';
  else {
    if (x < 0) obuf[opt++] = '-', x = -x;
    int sn = 0;
    while (x) str[sn++] = x % 10 + '0', x /= 10;
    for (int i = sn - 1; i >= 0; i--) obuf[opt++] = str[i];
  }
  if (opt >= (SIZE >> 1)) {
    fwrite(obuf, 1, opt, stdout);
    opt = 0;
  }
}
void write(unsigned long long x) {
  if (x == 0)
    obuf[opt++] = '0';
  else {
    int sn = 0;
    while (x) str[sn++] = x % 10 + '0', x /= 10;
    for (int i = sn - 1; i >= 0; i--) obuf[opt++] = str[i];
  }
  if (opt >= (SIZE >> 1)) {
    fwrite(obuf, 1, opt, stdout);
    opt = 0;
  }
}
void write(char x) {
  obuf[opt++] = x;
  if (opt >= (SIZE >> 1)) {
    fwrite(obuf, 1, opt, stdout);
    opt = 0;
  }
}
void Fflush() {
  if (opt) fwrite(obuf, 1, opt, stdout);
  opt = 0;
}
};  // namespace FastIO
const int N = 2200000;
const int M = 330;
struct DSU {
  static const int MX = 110000;
  int rnk[MX], par[MX], odd[MX], spoint, stk[2 * MX];
  int merged;
  void init() {
    for (int i = 0; i < MX; i++) par[i] = i, rnk[i] = 0, odd[i] = 0;
    spoint = 0;
    merged = 0;
  }
  int get(int x) {
    while (x != par[x]) x = par[x];
    return x;
  }
  int dis(int x) {
    int res = 0;
    while (x != par[x]) res = res ^ odd[x], x = par[x];
    return res;
  }
  void merge(int x, int y) {
    int px = get(x), py = get(y);
    if (px == py) return;
    merged++;
    int dx = dis(x), dy = dis(y);
    if (rnk[px] > rnk[py]) swap(px, py);
    if (rnk[px] == rnk[py]) {
      rnk[py]++;
      par[px] = py;
      odd[px] = dx ^ dy ^ 1;
      stk[spoint++] = px;
      stk[spoint++] = -py;
    } else {
      par[px] = py;
      odd[px] = dx ^ dy ^ 1;
      stk[spoint++] = px;
    }
  }
  void restore(int last) {
    while (spoint > last) {
      int x = stk[--spoint];
      if (x > 0) {
        par[x] = x;
        merged--;
      } else {
        rnk[-x]--;
      }
    }
  }
} dsu;
inline int get_id(int x, int y) { return x * M + y + 1; }
struct Data {
  int x, y, c;
  Data(int x = 0, int y = 0, int c = 0) : x(x), y(y), c(c) {}
} Q[N];
int vis[M][M], visT;
int val[M][M];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int n, m;
int ans[N];
void calc(int st, int en) {
  if (st == en) {
    int last = dsu.spoint;
    for (int d = 0; d < 4; d++) {
      int x = Q[st].x + dx[d], y = Q[st].y + dy[d];
      if (x < 0 || x >= n || y < 0 || y >= m) continue;
      if (val[x][y] == Q[st].c) {
        dsu.merge(get_id(Q[st].x, Q[st].y), get_id(x, y));
      }
    }
    ans[st] = n * m - dsu.merged;
    dsu.restore(last);
    return;
  }
  int mid = st + en >> 1;
  visT++;
  for (int i = st; i <= mid; i++) vis[Q[i].x][Q[i].y] = visT;
  {
    int last = dsu.spoint;
    for (int i = mid + 1; i <= en; i++)
      if (vis[Q[i].x][Q[i].y] != visT) {
        for (int d = 0; d < 4; d++) {
          int x = Q[i].x + dx[d], y = Q[i].y + dy[d];
          if (x < 0 || x >= n || y < 0 || y >= m) continue;
          if (vis[x][y] == visT || val[x][y] != val[Q[i].x][Q[i].y]) continue;
          dsu.merge(get_id(Q[i].x, Q[i].y), get_id(x, y));
        }
      }
    calc(st, mid);
    dsu.restore(last);
  }
  visT++;
  for (int i = mid + 1; i <= en; i++) vis[Q[i].x][Q[i].y] = visT;
  {
    int last = dsu.spoint;
    vector<int> save(mid - st + 1);
    for (int i = st; i <= mid; i++) save[i - st] = val[Q[i].x][Q[i].y];
    for (int i = st; i <= mid; i++) val[Q[i].x][Q[i].y] = Q[i].c;
    for (int i = st; i <= mid; i++)
      if (vis[Q[i].x][Q[i].y] != visT) {
        for (int d = 0; d < 4; d++) {
          int x = Q[i].x + dx[d], y = Q[i].y + dy[d];
          if (x < 0 || x >= n || y < 0 || y >= m) continue;
          if (vis[x][y] == visT || val[x][y] != val[Q[i].x][Q[i].y]) continue;
          dsu.merge(get_id(Q[i].x, Q[i].y), get_id(x, y));
        }
      }
    calc(mid + 1, en);
    dsu.restore(last);
    for (int i = st; i <= mid; i++) val[Q[i].x][Q[i].y] = save[i - st];
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int q;
  FastIO::read(n), FastIO::read(m), FastIO::read(q);
  for (int i = 0; i < q; i++)
    FastIO::read(Q[i].x), FastIO::read(Q[i].y), FastIO::read(Q[i].c), Q[i].x--,
        Q[i].y--;
  dsu.init();
  visT++;
  for (int i = 0; i < q; i++) vis[Q[i].x][Q[i].y] = visT;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (vis[i][j] != visT) {
        for (int d = 0; d < 4; d++) {
          int x = i + dx[d], y = j + dy[d];
          if (x < 0 || x >= n || y < 0 || y >= m) continue;
          if (vis[x][y] == visT) continue;
          int u = get_id(i, j), v = get_id(x, y);
          dsu.merge(u, v);
        }
      }
  calc(0, q - 1);
  for (int i = 0; i < q; i++) FastIO::write(ans[i]), FastIO::write('\n');
  FastIO::Fflush();
  return 0;
}