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;
const long long int INF = 9223372036854775807;
const long long int mod = 1e9 + 7;
long long int max3(long long int a, long long int b, long long int c) {
  return max(c, max(a, b));
}
long long int min3(long long int a, long long int b, long long int c) {
  return min(a, min(b, c));
}
long long int power(long long int x, long long int y, long long int mod1) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x) % mod1;
    y = y >> 1;
    x = (x * x) % mod1;
  }
  return res;
}
long long int logg(long long int a) {
  long long int x = 0;
  while (a > 1) {
    x++;
    a /= 2;
  }
  return x;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long int abso(long long int x) {
  if (x < 0) {
    return -x;
  }
  return x;
}
long long int ceiling(long long int a, long long int b) {
  if (a % b == 0) {
    return a / b;
  } else {
    return a / b + 1;
  }
}
long long int modinv(long long int x, long long int p) {
  return power(x, p - 2, p);
}
struct point {
  long long int x;
  long long int y;
};
long long int cross(point a, point b) { return a.x * b.y - b.x * a.y; }
bool ccw1(point p1, point p2) {
  if (cross(p1, p2) > 0) {
    return true;
  } else {
    return false;
  }
}
bool comp(point p1, point p2) {
  if (p1.x < p2.x) {
    return true;
  } else {
    if (p1.x > p2.x) {
      return false;
    } else {
      if (p1.y <= p2.y) {
        return true;
      }
      return false;
    }
  }
}
long long ccw(point p1, point p2, point p3) {
  long long int val =
      (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
  return val;
}
void ccw_sort(vector<point> &v) {
  vector<point> v1, v2;
  for (int i = 0; i < v.size(); i++) {
    if (v[i].y > 0) {
      v1.push_back(v[i]);
    } else {
      v2.push_back(v[i]);
    }
  }
  sort(v1.begin(), v1.end(), ccw1);
  sort(v2.begin(), v2.end(), ccw1);
  for (int i = 0; i < v2.size(); i++) {
    v1.push_back(v2[i]);
  }
  v = v1;
}
int union_set(vector<vector<pair<int, int>>> &dsets, vector<vector<int>> &grp,
              int x1, int y1, int x2, int y2) {
  int grp1 = grp[x1][y1];
  int grp2 = grp[x2][y2];
  if (grp1 == grp2) {
    return 0;
  } else {
    if (dsets[grp1].size() < dsets[grp2].size()) {
      for (int k = 0; k < dsets[grp1].size(); k++) {
        dsets[grp2].push_back(dsets[grp1][k]);
        grp[dsets[grp1][k].first][dsets[grp1][k].second] = grp2;
      }
      dsets[grp1].resize(0);
    } else {
      int temp = grp2;
      grp2 = grp1;
      grp1 = temp;
      for (int k = 0; k < dsets[grp1].size(); k++) {
        dsets[grp2].push_back(dsets[grp1][k]);
        grp[dsets[grp1][k].first][dsets[grp1][k].second] = grp2;
      }
      dsets[grp1].resize(0);
    }
    return 1;
  }
}
int main() {
  int n, m, q;
  scanf("%d %d %d", &n, &m, &q);
  vector<vector<int>> st_state(n);
  vector<vector<int>> end_state(n);
  for (int j = 0; j < n; j++) {
    st_state[j].resize(m, 0);
    end_state[j].resize(m, 0);
  }
  vector<pair<pair<int, int>, int>> v;
  v.push_back(make_pair(make_pair(0, 0), 0));
  int num = 1;
  vector<bool> vv;
  vv.push_back(false);
  vector<vector<int>> col(max((int)1000, (int)2e6 / (n * m)) + 1);
  for (int i = 0; i < q; i++) {
    int x, y, c;
    scanf("%d %d %d", &x, &y, &c);
    x--;
    y--;
    v.push_back(make_pair(make_pair(x, y), c));
    col[end_state[x][y]].push_back(num);
    col[c].push_back(num);
    if (end_state[x][y] == c) {
      vv.push_back(false);
    } else {
      vv.push_back(true);
    }
    end_state[x][y] = c;
    num++;
  }
  q++;
  vector<vector<int>> grp(n);
  vector<vector<pair<int, int>>> dsets(n * m + 1);
  int fin_comps = n * m;
  for (int j = 0; j < n; j++) {
    grp[j].resize(m, 0);
    for (int k = 0; k < m; k++) {
      grp[j][k] = j * m + k;
      dsets[grp[j][k]].push_back(make_pair(j, k));
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i - 1 >= 0 && end_state[i - 1][j] == end_state[i][j]) {
        fin_comps -= union_set(dsets, grp, i - 1, j, i, j);
      }
      if (i + 1 <= n - 1 && end_state[i + 1][j] == end_state[i][j]) {
        fin_comps -= union_set(dsets, grp, i + 1, j, i, j);
      }
      if (j + 1 <= m - 1 && end_state[i][j + 1] == end_state[i][j]) {
        fin_comps -= union_set(dsets, grp, i, j + 1, i, j);
      }
      if (j - 1 >= 0 && end_state[i][j - 1] == end_state[i][j]) {
        fin_comps -= union_set(dsets, grp, i, j - 1, i, j);
      }
    }
  }
  int i = 0;
  vector<int> ans_vec(q + 1);
  ans_vec[q] = fin_comps;
  while (i < q) {
    int j = i;
    while (j < q && v[i].second == v[j].second) {
      j++;
    }
    int c = v[i].second;
    vector<vector<int>> temp_grp(n + 1);
    vector<vector<pair<int, int>>> temp_dsets(n * m);
    auto temp_state = end_state;
    int num_sets = 0;
    for (int i = 0; i < n; i++) {
      temp_grp[i].resize(m);
      for (int j = 0; j < m; j++) {
        if (end_state[i][j] == c) {
          temp_grp[i][j] = num_sets;
          temp_dsets[num_sets].push_back(make_pair(i, j));
          num_sets++;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (end_state[i][j] == c) {
          if (i - 1 >= 0 && end_state[i - 1][j] == end_state[i][j]) {
            union_set(temp_dsets, temp_grp, i - 1, j, i, j);
          }
          if (i + 1 <= n - 1 && end_state[i + 1][j] == end_state[i][j]) {
            union_set(temp_dsets, temp_grp, i + 1, j, i, j);
          }
          if (j + 1 <= m - 1 && end_state[i][j + 1] == end_state[i][j]) {
            union_set(temp_dsets, temp_grp, i, j + 1, i, j);
          }
          if (j - 1 >= 0 && end_state[i][j - 1] == end_state[i][j]) {
            union_set(temp_dsets, temp_grp, i, j - 1, i, j);
          }
        }
      }
    }
    for (int k = (int)col[c].size() - 1; k >= 0 && col[c][k] >= j; k--) {
      int comp_red = -1;
      if (!vv[col[c][k]]) continue;
      int i = v[col[c][k]].first.first;
      int j = v[col[c][k]].first.second;
      temp_grp[i][j] = num_sets;
      temp_dsets[num_sets].push_back(make_pair(i, j));
      num_sets++;
      if (i - 1 >= 0 && temp_state[i - 1][j] == c) {
        comp_red += union_set(temp_dsets, temp_grp, i - 1, j, i, j);
      }
      if (i + 1 <= n - 1 && temp_state[i + 1][j] == c) {
        comp_red += union_set(temp_dsets, temp_grp, i + 1, j, i, j);
      }
      if (j + 1 <= m - 1 && temp_state[i][j + 1] == c) {
        comp_red += union_set(temp_dsets, temp_grp, i, j + 1, i, j);
      }
      if (j - 1 >= 0 && temp_state[i][j - 1] == c) {
        comp_red += union_set(temp_dsets, temp_grp, i, j - 1, i, j);
      }
      auto cur_q = v[col[c][k]];
      temp_state[cur_q.first.first][cur_q.first.second] = c;
      ans_vec[col[c][k]] -= comp_red;
      comp_red = 0;
    }
    num_sets = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        temp_dsets[i * m + j].resize(0);
        temp_grp[i][j] = 0;
        if (st_state[i][j] == c) {
          temp_grp[i][j] = num_sets;
          temp_dsets[num_sets].push_back(make_pair(i, j));
          num_sets++;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (st_state[i][j] == c) {
          if (i - 1 >= 0 && st_state[i - 1][j] == st_state[i][j]) {
            union_set(temp_dsets, temp_grp, i - 1, j, i, j);
          }
          if (i + 1 <= n - 1 && st_state[i + 1][j] == st_state[i][j]) {
            union_set(temp_dsets, temp_grp, i + 1, j, i, j);
          }
          if (j + 1 <= m - 1 && st_state[i][j + 1] == st_state[i][j]) {
            union_set(temp_dsets, temp_grp, i, j + 1, i, j);
          }
          if (j - 1 >= 0 && st_state[i][j - 1] == st_state[i][j]) {
            union_set(temp_dsets, temp_grp, i, j - 1, i, j);
          }
        }
      }
    }
    int ind = -1;
    auto temp_temp_dsets = temp_dsets;
    auto temp_temp_grp = temp_grp;
    int num_sets1 = num_sets;
    for (int k = 0; k < col[c].size(); k++) {
      if (col[c][k] == i) {
        ind = k;
        break;
      }
    }
    temp_state = st_state;
    for (int k = ind - 1; k >= 0; k--) {
      int comp_red = -1;
      if (!vv[col[c][k]]) continue;
      int i = v[col[c][k]].first.first;
      int j = v[col[c][k]].first.second;
      temp_grp[i][j] = num_sets;
      temp_dsets[num_sets].push_back(make_pair(i, j));
      num_sets++;
      if (i - 1 >= 0 && temp_state[i - 1][j] == temp_state[i][j]) {
        comp_red += union_set(temp_dsets, temp_grp, i - 1, j, i, j);
      }
      if (i + 1 <= n - 1 && temp_state[i + 1][j] == temp_state[i][j]) {
        comp_red += union_set(temp_dsets, temp_grp, i + 1, j, i, j);
      }
      if (j + 1 <= m - 1 && temp_state[i][j + 1] == temp_state[i][j]) {
        comp_red += union_set(temp_dsets, temp_grp, i, j + 1, i, j);
      }
      if (j - 1 >= 0 && temp_state[i][j - 1] == temp_state[i][j]) {
        comp_red += union_set(temp_dsets, temp_grp, i, j - 1, i, j);
      }
      auto cur_q = v[col[c][k]];
      temp_state[cur_q.first.first][cur_q.first.second] = c;
      ans_vec[col[c][k]] -= comp_red;
      comp_red = 0;
    }
    num_sets = num_sets1;
    for (int k = i; k < j; k++) {
      int comp_red = -1;
      if (!vv[k]) continue;
      int i1 = v[k].first.first;
      int j1 = v[k].first.second;
      temp_temp_grp[i1][j1] = num_sets;
      temp_temp_dsets[num_sets].push_back(make_pair(i1, j1));
      num_sets++;
      if (i1 - 1 >= 0 && st_state[i1 - 1][j1] == c) {
        comp_red +=
            union_set(temp_temp_dsets, temp_temp_grp, i1 - 1, j1, i1, j1);
      }
      if (i1 + 1 <= n - 1 && st_state[i1 + 1][j1] == c) {
        comp_red +=
            union_set(temp_temp_dsets, temp_temp_grp, i1 + 1, j1, i1, j1);
      }
      if (j1 + 1 <= m - 1 && st_state[i1][j1 + 1] == c) {
        comp_red +=
            union_set(temp_temp_dsets, temp_temp_grp, i1, j1 + 1, i1, j1);
      }
      if (j1 - 1 >= 0 && st_state[i1][j1 - 1] == c) {
        comp_red +=
            union_set(temp_temp_dsets, temp_temp_grp, i1, j1 - 1, i1, j1);
      }
      auto cur_q = v[k];
      st_state[cur_q.first.first][cur_q.first.second] = c;
      ans_vec[k] += comp_red;
      comp_red = 0;
    }
    i = j;
  }
  ans_vec[q] = fin_comps;
  for (int j = (int)ans_vec.size() - 2; j >= 0; j--) {
    ans_vec[j] += ans_vec[j + 1];
  }
  for (int j = 2; j < ans_vec.size(); j++) {
    printf("%d\n", ans_vec[j]);
  }
}