#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, SZ = 1 << 18,
          MAX_SIZE = 1 << 20;
int op, tot, BS, N, M, Q, A[300][300], V[2000000], cnt[300 * 300],
    color[300 * 300], L[300][300][4];
vector<pair<int, int>> tree[2 * SZ];
vector<int> B;
char buf[MAX_SIZE], obuf[MAX_SIZE];
inline char get_char() {
  static int p = 0, s = 0;
  if (p == s) {
    p = 0;
    s = fread(buf, 1, MAX_SIZE, stdin);
    if (p == s) return 0;
  }
  return buf[p++];
}
inline int get_int() {
  int ret = 0;
  bool is_negative = false;
  char c = -1;
  while (('0' > c || c > '9') && c != '-') c = get_char();
  if (c == '-') {
    is_negative = true;
    c = get_char();
  }
  while ('0' <= c && c <= '9') ret *= 10, ret += c - '0', c = get_char();
  return (is_negative ? -ret : ret);
}
inline void flush_output() {
  if (op) fwrite(obuf, 1, op, stdout), op = 0;
}
inline void put_char(char c) {
  if (op == MAX_SIZE) flush_output();
  obuf[op++] = c;
}
inline void print_int(int n) {
  static char temp[30];
  bool is_negative = n < 0;
  int c = 29;
  if (n == 0)
    put_char('0');
  else {
    for (n = abs(n); n; n /= 10) temp[c--] = n % 10 + '0';
    if (is_negative) put_char('-');
    while (++c < 30) put_char(temp[c]);
  }
  put_char('\n');
}
bool valid_coord(int x, int y) { return 0 <= x && x < N && 0 <= y && y < M; }
int convert(int x, int y) { return x * M + y; }
void add_edge(int s, int e, int a, int b) {
  for (s += SZ, e += SZ; s <= e; s >>= 1, e >>= 1) {
    if (s & 1) tree[s++].emplace_back(a, b);
    if (~e & 1) tree[e--].emplace_back(a, b);
  }
}
int find_(int a) {
  while (color[a] != a) a = color[a];
  return a;
}
void union_(int a, int b) {
  if (cnt[a] > cnt[b]) swap(a, b);
  cnt[b] += cnt[a];
  color[a] = b;
  B.push_back(a);
  tot--;
}
void solve(int bit, int s, int e) {
  int m = (s + e) >> 1, bsz = B.size();
  if (BS + s >= Q) return;
  for (auto &[a, b] : tree[bit])
    if ((a = find_(a)) != (b = find_(b))) union_(a, b);
  if (s < e) {
    solve(2 * bit, s, m);
    solve(2 * bit + 1, m + 1, e);
  } else
    print_int(tot);
  while (B.size() > bsz) {
    int c = B.back();
    B.pop_back();
    cnt[color[c]] -= cnt[c];
    color[c] = c;
    tot++;
  }
}
int main() {
  N = get_int();
  M = get_int();
  Q = get_int();
  tot = N * M;
  memset(L, -1, sizeof(L));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) {
      cnt[color[convert(i, j)] = convert(i, j)] = 1;
      if (i && A[i][j] == A[i - 1][j]) L[i][j][0] = L[i - 1][j][2] = 0;
      if (j && A[i][j] == A[i][j - 1]) L[i][j][1] = L[i][j - 1][3] = 0;
    }
  for (int c = 0; c < Q; c++) {
    int x = get_int() - 1, y = get_int() - 1;
    V[c] = get_int();
    for (int k = 0; k < 4; k++)
      if (valid_coord(x + dx[k], y + dy[k]) &&
          A[x][y] == A[x + dx[k]][y + dy[k]]) {
        int a = convert(x, y), b = convert(x + dx[k], y + dy[k]);
        if (a > b) swap(a, b);
        add_edge(L[x][y][k], c % SZ - 1, a, b);
        L[x][y][k] = L[x + dx[k]][y + dy[k]][k ^ 2] = -1;
      }
    A[x][y] = V[c];
    for (int k = 0; k < 4; k++)
      if (valid_coord(x + dx[k], y + dy[k]) &&
          A[x][y] == A[x + dx[k]][y + dy[k]])
        L[x][y][k] = L[x + dx[k]][y + dy[k]][k ^ 2] = c % SZ;
    if ((c + 1) % SZ == 0) {
      for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
          if (L[i][j][0] > -1)
            add_edge(L[i][j][0], SZ - 1, convert(i - 1, j), convert(i, j));
          if (L[i][j][1] > -1)
            add_edge(L[i][j][1], SZ - 1, convert(i, j - 1), convert(i, j));
        }
      solve(1, 0, SZ - 1);
      BS += SZ;
      memset(L, -1, sizeof(L));
      for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
          if (i && A[i][j] == A[i - 1][j]) L[i][j][0] = L[i - 1][j][2] = 0;
          if (j && A[i][j] == A[i][j - 1]) L[i][j][1] = L[i][j - 1][3] = 0;
        }
      for (int i = 2 * SZ; --i;) tree[i].clear();
    }
  }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) {
      if (L[i][j][0] > -1)
        add_edge(L[i][j][0], SZ - 1, convert(i - 1, j), convert(i, j));
      if (L[i][j][1] > -1)
        add_edge(L[i][j][1], SZ - 1, convert(i, j - 1), convert(i, j));
    }
  solve(1, 0, SZ - 1);
  flush_output();
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, SZ = 1 << 18,
          MAX_SIZE = 1 << 20;
int op, tot, BS, N, M, Q, A[300][300], V[2000000], cnt[300 * 300],
    color[300 * 300], L[300][300][4];
vector<pair<int, int>> tree[2 * SZ];
vector<int> B;
char buf[MAX_SIZE], obuf[MAX_SIZE];
inline char get_char() {
  static int p = 0, s = 0;
  if (p == s) {
    p = 0;
    s = fread(buf, 1, MAX_SIZE, stdin);
    if (p == s) return 0;
  }
  return buf[p++];
}
inline int get_int() {
  int ret = 0;
  bool is_negative = false;
  char c = -1;
  while (('0' > c || c > '9') && c != '-') c = get_char();
  if (c == '-') {
    is_negative = true;
    c = get_char();
  }
  while ('0' <= c && c <= '9') ret *= 10, ret += c - '0', c = get_char();
  return (is_negative ? -ret : ret);
}
inline void flush_output() {
  if (op) fwrite(obuf, 1, op, stdout), op = 0;
}
inline void put_char(char c) {
  if (op == MAX_SIZE) flush_output();
  obuf[op++] = c;
}
inline void print_int(int n) {
  static char temp[30];
  bool is_negative = n < 0;
  int c = 29;
  if (n == 0)
    put_char('0');
  else {
    for (n = abs(n); n; n /= 10) temp[c--] = n % 10 + '0';
    if (is_negative) put_char('-');
    while (++c < 30) put_char(temp[c]);
  }
  put_char('\n');
}
bool valid_coord(int x, int y) { return 0 <= x && x < N && 0 <= y && y < M; }
int convert(int x, int y) { return x * M + y; }
void add_edge(int s, int e, int a, int b) {
  for (s += SZ, e += SZ; s <= e; s >>= 1, e >>= 1) {
    if (s & 1) tree[s++].emplace_back(a, b);
    if (~e & 1) tree[e--].emplace_back(a, b);
  }
}
int find_(int a) {
  while (color[a] != a) a = color[a];
  return a;
}
void union_(int a, int b) {
  if (cnt[a] > cnt[b]) swap(a, b);
  cnt[b] += cnt[a];
  color[a] = b;
  B.push_back(a);
  tot--;
}
void solve(int bit, int s, int e) {
  int m = (s + e) >> 1, bsz = B.size();
  if (BS + s >= Q) return;
  for (auto &[a, b] : tree[bit])
    if ((a = find_(a)) != (b = find_(b))) union_(a, b);
  if (s < e) {
    solve(2 * bit, s, m);
    solve(2 * bit + 1, m + 1, e);
  } else
    print_int(tot);
  while (B.size() > bsz) {
    int c = B.back();
    B.pop_back();
    cnt[color[c]] -= cnt[c];
    color[c] = c;
    tot++;
  }
}
int main() {
  N = get_int();
  M = get_int();
  Q = get_int();
  tot = N * M;
  memset(L, -1, sizeof(L));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) {
      cnt[color[convert(i, j)] = convert(i, j)] = 1;
      if (i && A[i][j] == A[i - 1][j]) L[i][j][0] = L[i - 1][j][2] = 0;
      if (j && A[i][j] == A[i][j - 1]) L[i][j][1] = L[i][j - 1][3] = 0;
    }
  for (int c = 0; c < Q; c++) {
    int x = get_int() - 1, y = get_int() - 1;
    V[c] = get_int();
    for (int k = 0; k < 4; k++)
      if (valid_coord(x + dx[k], y + dy[k]) &&
          A[x][y] == A[x + dx[k]][y + dy[k]]) {
        int a = convert(x, y), b = convert(x + dx[k], y + dy[k]);
        if (a > b) swap(a, b);
        add_edge(L[x][y][k], c % SZ - 1, a, b);
        L[x][y][k] = L[x + dx[k]][y + dy[k]][k ^ 2] = -1;
      }
    A[x][y] = V[c];
    for (int k = 0; k < 4; k++)
      if (valid_coord(x + dx[k], y + dy[k]) &&
          A[x][y] == A[x + dx[k]][y + dy[k]])
        L[x][y][k] = L[x + dx[k]][y + dy[k]][k ^ 2] = c % SZ;
    if ((c + 1) % SZ == 0) {
      for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
          if (L[i][j][0] > -1)
            add_edge(L[i][j][0], SZ - 1, convert(i - 1, j), convert(i, j));
          if (L[i][j][1] > -1)
            add_edge(L[i][j][1], SZ - 1, convert(i, j - 1), convert(i, j));
        }
      solve(1, 0, SZ - 1);
      BS += SZ;
      memset(L, -1, sizeof(L));
      for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
          if (i && A[i][j] == A[i - 1][j]) L[i][j][0] = L[i - 1][j][2] = 0;
          if (j && A[i][j] == A[i][j - 1]) L[i][j][1] = L[i][j - 1][3] = 0;
        }
      for (int i = 2 * SZ; --i;) tree[i].clear();
    }
  }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) {
      if (L[i][j][0] > -1)
        add_edge(L[i][j][0], SZ - 1, convert(i - 1, j), convert(i, j));
      if (L[i][j][1] > -1)
        add_edge(L[i][j][1], SZ - 1, convert(i, j - 1), convert(i, j));
    }
  solve(1, 0, SZ - 1);
  flush_output();
  return 0;
}

```