#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
struct monostate {
  friend istream& operator>>(istream& is, const monostate& ms) { return is; }
  friend ostream& operator<<(ostream& os, const monostate& ms) { return os; }
  friend monostate operator+(const monostate& a, const monostate& b) {
    return a;
  }
} ms;
#pragma GCC diagnostic pop
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T& number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T& number, Args&... args) {
  read_int(number);
  read_int(args...);
}
}  // namespace IO
struct union_find {
  struct node {
    int par, rnk, size;
    node(int id = 0) : par(id), rnk(0), size(1) {}
  };
  vector<node> uf;
  union_find(int N = 0) : uf(N) {
    for (int i = 0; i < N; i++) uf[i] = node(i);
  }
  int rep(int i) {
    if (i != uf[i].par) uf[i].par = rep(uf[i].par);
    return uf[i].par;
  }
  bool unio(int a, int b) {
    a = rep(a), b = rep(b);
    if (a == b) return false;
    if (uf[a].rnk < uf[b].rnk) swap(a, b);
    uf[b].par = a;
    uf[a].size += uf[b].size;
    if (uf[a].rnk == uf[b].rnk) uf[a].rnk++;
    return true;
  }
  node& operator[](int i) { return uf[rep(i)]; }
  friend void pr(const union_find& u) {
    pr("{");
    bool first = 1;
    for (int i = 0; i < int((u.uf).size()); i++)
      if (u.uf[i].par == i) {
        if (!first)
          pr(", ");
        else
          first = 0;
        pr("[ ", i, " | rank=", u.uf[i].rnk, " size=", u.uf[i].size, " ]");
      }
    pr("}");
  }
};
int main() {
  setIO();
  int N, M, Q;
  IO::read_int(N, M, Q);
  struct event {
    int x, y, i;
    bool ins;
  };
  const int MAXC = 2e6 + 1;
  vector<vector<event>> evs(MAXC);
  vvi color(N, vi(M));
  for (int q = 0; q < (Q); q++) {
    int x, y, c;
    IO::read_int(x, y, c);
    --x, --y;
    if (color[x][y] != c) {
      evs[color[x][y]].push_back({x, y, q, 0});
      color[x][y] = c;
      evs[c].push_back({x, y, q, 1});
    }
  }
  int cc = 0;
  vector<vb> active(N, vb(M));
  union_find uf(N * M);
  auto clear = [&]() {
    for (auto& e : active) fill((e).begin(), (e).end(), 0);
    for (int i = 0; i < (N * M); i++) {
      uf.uf[i].par = i;
      uf.uf[i].rnk = 0;
      uf.uf[i].size = 1;
    }
    cc = 0;
  };
  auto index = [&](int r, int c) {
    if (r < 0 || c < 0 || r == N || c == M) return -1;
    if (!active[r][c]) return -1;
    return r * M + c;
  };
  auto insert = [&](int r, int c) {
    assert(!active[r][c]);
    active[r][c] = 1;
    cc += 1;
    int loc = index(r, c);
    if (int nbr = index(r - 1, c); nbr != -1) cc -= uf.unio(loc, nbr);
    if (int nbr = index(r + 1, c); nbr != -1) cc -= uf.unio(loc, nbr);
    if (int nbr = index(r, c - 1); nbr != -1) cc -= uf.unio(loc, nbr);
    if (int nbr = index(r, c + 1); nbr != -1) cc -= uf.unio(loc, nbr);
  };
  vi diff(Q);
  for (int col = 0; col < (MAXC); col++)
    if (!evs[col].empty()) {
      {
        clear();
        for (auto [x, y, q, ins] : evs[col]) {
          if (!ins) break;
          int bef = cc;
          insert(x, y);
          diff[q] += cc - bef;
        }
      }
      reverse((evs[col]).begin(), (evs[col]).end());
      {
        clear();
        for (int r = 0; r < (N); r++)
          for (int c = 0; c < (M); c++)
            if (color[r][c] == col) insert(r, c);
        for (auto [x, y, q, ins] : evs[col]) {
          if (ins) break;
          int bef = cc;
          insert(x, y);
          diff[q] += bef - cc;
        }
      }
    }
  int ans = 1;
  for (auto& d : diff) {
    ps(ans += d);
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
struct monostate {
  friend istream& operator>>(istream& is, const monostate& ms) { return is; }
  friend ostream& operator<<(ostream& os, const monostate& ms) { return os; }
  friend monostate operator+(const monostate& a, const monostate& b) {
    return a;
  }
} ms;
#pragma GCC diagnostic pop
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T& number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T& number, Args&... args) {
  read_int(number);
  read_int(args...);
}
}  // namespace IO
struct union_find {
  struct node {
    int par, rnk, size;
    node(int id = 0) : par(id), rnk(0), size(1) {}
  };
  vector<node> uf;
  union_find(int N = 0) : uf(N) {
    for (int i = 0; i < N; i++) uf[i] = node(i);
  }
  int rep(int i) {
    if (i != uf[i].par) uf[i].par = rep(uf[i].par);
    return uf[i].par;
  }
  bool unio(int a, int b) {
    a = rep(a), b = rep(b);
    if (a == b) return false;
    if (uf[a].rnk < uf[b].rnk) swap(a, b);
    uf[b].par = a;
    uf[a].size += uf[b].size;
    if (uf[a].rnk == uf[b].rnk) uf[a].rnk++;
    return true;
  }
  node& operator[](int i) { return uf[rep(i)]; }
  friend void pr(const union_find& u) {
    pr("{");
    bool first = 1;
    for (int i = 0; i < int((u.uf).size()); i++)
      if (u.uf[i].par == i) {
        if (!first)
          pr(", ");
        else
          first = 0;
        pr("[ ", i, " | rank=", u.uf[i].rnk, " size=", u.uf[i].size, " ]");
      }
    pr("}");
  }
};
int main() {
  setIO();
  int N, M, Q;
  IO::read_int(N, M, Q);
  struct event {
    int x, y, i;
    bool ins;
  };
  const int MAXC = 2e6 + 1;
  vector<vector<event>> evs(MAXC);
  vvi color(N, vi(M));
  for (int q = 0; q < (Q); q++) {
    int x, y, c;
    IO::read_int(x, y, c);
    --x, --y;
    if (color[x][y] != c) {
      evs[color[x][y]].push_back({x, y, q, 0});
      color[x][y] = c;
      evs[c].push_back({x, y, q, 1});
    }
  }
  int cc = 0;
  vector<vb> active(N, vb(M));
  union_find uf(N * M);
  auto clear = [&]() {
    for (auto& e : active) fill((e).begin(), (e).end(), 0);
    for (int i = 0; i < (N * M); i++) {
      uf.uf[i].par = i;
      uf.uf[i].rnk = 0;
      uf.uf[i].size = 1;
    }
    cc = 0;
  };
  auto index = [&](int r, int c) {
    if (r < 0 || c < 0 || r == N || c == M) return -1;
    if (!active[r][c]) return -1;
    return r * M + c;
  };
  auto insert = [&](int r, int c) {
    assert(!active[r][c]);
    active[r][c] = 1;
    cc += 1;
    int loc = index(r, c);
    if (int nbr = index(r - 1, c); nbr != -1) cc -= uf.unio(loc, nbr);
    if (int nbr = index(r + 1, c); nbr != -1) cc -= uf.unio(loc, nbr);
    if (int nbr = index(r, c - 1); nbr != -1) cc -= uf.unio(loc, nbr);
    if (int nbr = index(r, c + 1); nbr != -1) cc -= uf.unio(loc, nbr);
  };
  vi diff(Q);
  for (int col = 0; col < (MAXC); col++)
    if (!evs[col].empty()) {
      {
        clear();
        for (auto [x, y, q, ins] : evs[col]) {
          if (!ins) break;
          int bef = cc;
          insert(x, y);
          diff[q] += cc - bef;
        }
      }
      reverse((evs[col]).begin(), (evs[col]).end());
      {
        clear();
        for (int r = 0; r < (N); r++)
          for (int c = 0; c < (M); c++)
            if (color[r][c] == col) insert(r, c);
        for (auto [x, y, q, ins] : evs[col]) {
          if (ins) break;
          int bef = cc;
          insert(x, y);
          diff[q] += bef - cc;
        }
      }
    }
  int ans = 1;
  for (auto& d : diff) {
    ps(ans += d);
  }
  return 0;
}

```