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;
template <class T>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
struct UnionFind {
  int n, cc, *u;
  UnionFind() : n(0), cc(0), u(NULL) {}
  UnionFind(int n_) : n(n_), cc(n_) {
    u = new int[n_];
    memset(u, -1, sizeof(int) * n);
  }
  UnionFind(const UnionFind &y) : n(y.n), cc(y.cc) {
    u = new int[y.n];
    memcpy(u, y.u, sizeof(int) * n);
  }
  ~UnionFind() {
    delete[] u;
    u = NULL;
    n = cc = 0;
  }
  friend void swap(UnionFind &x, UnionFind &y) {
    swap(x.n, y.n);
    swap(x.cc, y.cc);
    swap(x.u, y.u);
  }
  UnionFind &operator=(UnionFind y) {
    swap(*this, y);
    return *this;
  }
  void init() {
    cc = n;
    memset(u, -1, sizeof(int) * n);
  }
  int root(int x) {
    int y = x, t;
    while (u[y] >= 0) y = u[y];
    while (x != y) {
      t = u[x];
      u[x] = y;
      x = t;
    }
    return y;
  }
  bool link(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (u[y] < u[x]) swap(x, y);
    u[x] += u[y];
    u[y] = x;
    cc--;
    return true;
  }
  bool same(int x, int y) { return root(x) == root(y); }
  int size(int x) { return -u[root(x)]; }
  int count() { return cc; }
};
int N, M;
int Q;
vector<pair<int, int> > H[311][311];
bool in(int y, int x) { return 0 <= y && y < N && 0 <= x && x < M; }
struct Data {
  int y, x;
  int start, end;
  Data() {}
  Data(int y_, int x_, int start_, int end_) {
    y = y_;
    x = x_;
    start = start_;
    end = end_;
  }
};
vector<Data> C[2000011];
struct ByStart {
  bool operator()(const Data &a, const Data &b) const {
    return a.start < b.start;
  }
} byStart;
struct ByEndRev {
  bool operator()(const Data &a, const Data &b) const { return a.end > b.end; }
} byEndRev;
int F[2000011];
int name[311][311];
int mark[311][311];
void MAIN() {
  scanf("%d%d%d", &N, &M, &Q);
  for (int i = 0, i_len = (N); i < i_len; ++i)
    for (int j = 0, j_len = (M); j < j_len; ++j) H[i][j].emplace_back(0, 0);
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    int x, y, c;
    scanf("%d%d%d", &y, &x, &c);
    x--;
    y--;
    if (H[y][x].back().second != c) {
      H[y][x].emplace_back(i + 1, c);
    }
  }
  for (int y = 0, y_len = (N); y < y_len; ++y)
    for (int x = 0, x_len = (M); x < x_len; ++x) {
      for (int k = 0, k_len = (H[y][x].size()); k < k_len; ++k) {
        int start = H[y][x][k].first;
        int color = H[y][x][k].second;
        int end;
        if (k + 1 == (int)H[y][x].size())
          end = Q + 1;
        else
          end = H[y][x][k + 1].first;
        C[color].emplace_back(y, x, start, end);
      }
    }
  int marker = 0;
  for (int color = 0, color_len = (2000011); color < color_len; ++color)
    if (!C[color].empty()) {
      auto V = C[color];
      int mid = V[0].end;
      for (__typeof((V).begin()) e = (V).begin(), e_end = (V).end(); e != e_end;
           ++e)
        amin(mid, e->end);
      sort(V.begin(), V.end(), byStart);
      int cc = 0;
      int cnt = 0;
      marker++;
      UnionFind U(V.size());
      for (int z = 0; z < (int)V.size();) {
        int i = z;
        while (i < (int)V.size() && V[z].start == V[i].start) {
          int y = V[i].y, x = V[i].x;
          name[y][x] = cnt++;
          cc++;
          mark[y][x] = marker;
          for (int d = 0, d_len = (4); d < d_len; ++d) {
            int yy = y + dy[d];
            int xx = x + dx[d];
            if (in(yy, xx) && mark[yy][xx] == marker) {
              if (!U.same(name[y][x], name[yy][xx])) {
                U.link(name[y][x], name[yy][xx]);
                cc--;
              }
            }
          }
          i++;
        }
        int end;
        if (i == (int)V.size())
          end = mid;
        else
          end = V[i].start;
        F[V[z].start] += cc;
        F[end] -= cc;
        z = i;
      }
      int cc_task_1 = cc;
      sort(V.begin(), V.end(), byEndRev);
      cc = 0;
      cnt = 0;
      marker++;
      U.init();
      for (int z = 0; z < (int)V.size();) {
        int i = z;
        while (i < (int)V.size() && V[z].end == V[i].end) {
          int y = V[i].y, x = V[i].x;
          name[y][x] = cnt++;
          cc++;
          mark[y][x] = marker;
          for (int d = 0, d_len = (4); d < d_len; ++d) {
            int yy = y + dy[d];
            int xx = x + dx[d];
            if (in(yy, xx) && mark[yy][xx] == marker) {
              if (!U.same(name[y][x], name[yy][xx])) {
                U.link(name[y][x], name[yy][xx]);
                cc--;
              }
            }
          }
          i++;
        }
        int start;
        if (i == (int)V.size())
          start = mid;
        else
          start = V[i].end;
        F[start] += cc;
        F[V[z].end] -= cc;
        z = i;
      }
      assert(cc_task_1 == cc);
    }
  for (int i = 0, i_len = (Q + 1); i < i_len; ++i) F[i + 1] += F[i];
  for (int i = 1; i <= Q; i++) printf("%d\n", F[i]);
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}