#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.1415926535897932384626433;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T> >;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
struct maintainer {
  int n, bad, good, empty;
  vector<vector<vector<int> > > v;
  vector<bool> is_bad, is_good, is_empty;
  maintainer(int n) {
    this->n = n;
    bad = good = 0;
    empty = n;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      v[i].resize(2);
      for (int j = 0; j < 2; j++) v[i][j].resize(2);
    }
    is_bad.resize(n + 1, false);
    is_good.resize(n + 1, false);
    is_empty.resize(n + 1, true);
  }
  void add(int r, int c, int val) {
    c &= 1;
    if (is_empty[r]) {
      is_empty[r] = 0;
      empty--;
      is_good[r] = 1;
      good++;
    } else if (is_good[r]) {
      if (v[r][c][1 ^ val] > 0 || v[r][1 ^ c][val] > 0) {
        is_good[r] = 0;
        good--;
        is_bad[r] = 1;
        bad++;
      }
    }
    v[r][c][val]++;
  }
  void rem(int r, int c, int val) {
    c &= 1;
    if (v[r][0][0] + v[r][0][1] + v[r][1][0] + v[r][1][1] == 1) {
      is_good[r] = 0;
      good--;
      is_empty[r] = 1;
      empty++;
      v[r][c][val]--;
    } else if (is_bad[r]) {
      v[r][c][val]--;
      if ((v[r][0][0] == 0 || v[r][0][1] == 0) &&
          (v[r][1][0] == 0 || v[r][1][1] == 0) &&
          (v[r][0][0] == 0 || v[r][1][0] == 0) &&
          (v[r][0][1] == 0 || v[r][1][1] == 0)) {
        is_bad[r] = 0;
        bad--;
        is_good[r] = 1;
        good++;
      }
    } else
      v[r][c][val]--;
  }
  int get_empty_rows() {
    if (bad > 0) return -1;
    return empty;
  }
};
const long long N = 1e6 + 6, p = 998244353;
long long pw[N], n, m, k, x[2][2];
bool have_common() {
  if ((x[0][0] == 0 || x[0][1] == 0) && (x[1][0] == 0 || x[1][1] == 0) &&
      (x[0][0] == 0 || x[1][0] == 0) && (x[0][1] == 0 || x[1][1] == 0))
    return 1;
  return 0;
}
long long add(long long val1, long long val2) {
  long long res = val1 + val2;
  if (res >= p) res -= p;
  return res;
}
long long sub(long long val1, long long val2) {
  long long res = val1 - val2;
  if (res < 0) res += p;
  return res;
}
void func() {
  cin >> n >> m >> k;
  long long z = max(n, m);
  pw[0] = 1;
  for (long long i = 1; i < z + 1; i++) pw[i] = (pw[i - 1] * 2LL) % p;
  maintainer rows(n), columns(m);
  map<pair<long long, long long>, long long> mp;
  for (long long i = 1; i < k + 1; i++) {
    int r, c, val;
    cin >> r >> c >> val;
    map<pair<long long, long long>, long long>::iterator it =
        mp.find(make_pair(r, c));
    if (it != mp.end()) {
      long long org_val = it->second;
      if (val == -1) {
        rows.rem(r, c, org_val);
        columns.rem(c, r, org_val);
        x[(r + c) & 1][org_val]--;
        mp.erase(it);
      } else if (val != org_val) {
        rows.rem(r, c, org_val);
        columns.rem(c, r, org_val);
        x[(r + c) & 1][org_val]--;
        rows.add(r, c, val);
        columns.add(c, r, val);
        x[(r + c) & 1][val]++;
        it->second = val;
      }
    } else {
      if (val != -1) {
        rows.add(r, c, val);
        columns.add(c, r, val);
        x[(r + c) & 1][val]++;
        mp[make_pair(r, c)] = val;
      }
    }
    long long val1 = rows.get_empty_rows(), val2 = columns.get_empty_rows();
    if (val1 == -1 && val2 == -1)
      cout << "0\n";
    else if (val1 != -1 && val2 != -1) {
      if ((long long)mp.size() > 0) {
        if (have_common())
          cout << sub(add(pw[val1], pw[val2]), 1) << "\n";
        else
          cout << add(pw[val1], pw[val2]) << "\n";
      } else
        cout << sub(add(pw[val1], pw[val2]), 2) << "\n";
    } else if (val1 != -1)
      cout << pw[val1] << "\n";
    else if (val2 != -1)
      cout << pw[val2] << "\n";
  }
}
int main() {
  {
    ios ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  }
  cout << fixed << setprecision(8);
  long long ntc = 1;
  for (long long i = 1; i < ntc + 1; i++) {
    func();
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

A matrix of size n × m, such that each cell of it contains either 0 or 1, is considered beautiful if the sum in every contiguous submatrix of size 2 × 2 is exactly 2, i. e. every "square" of size 2 × 2 contains exactly two 1's and exactly two 0's.

You are given a matrix of size n × m. Initially each cell of this matrix is empty. Let's denote the cell on the intersection of the x-th row and the y-th column as (x, y). You have to process the queries of three types:

  * x y -1 — clear the cell (x, y), if there was a number in it; 
  * x y 0 — write the number 0 in the cell (x, y), overwriting the number that was there previously (if any); 
  * x y 1 — write the number 1 in the cell (x, y), overwriting the number that was there previously (if any). 



After each query, print the number of ways to fill the empty cells of the matrix so that the resulting matrix is beautiful. Since the answers can be large, print them modulo 998244353.

Input

The first line contains three integers n, m and k (2 ≤ n, m ≤ 10^6; 1 ≤ k ≤ 3 ⋅ 10^5) — the number of rows in the matrix, the number of columns, and the number of queries, respectively.

Then k lines follow, the i-th of them contains three integers x_i, y_i, t_i (1 ≤ x_i ≤ n; 1 ≤ y_i ≤ m; -1 ≤ t_i ≤ 1) — the parameters for the i-th query.

Output

For each query, print one integer — the number of ways to fill the empty cells of the matrix after the respective query, taken modulo 998244353.

Example

Input


2 2 7
1 1 1
1 2 1
2 1 1
1 1 0
1 2 -1
2 1 -1
1 1 -1


Output


3
1
0
1
2
3
6

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.1415926535897932384626433;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T> >;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
struct maintainer {
  int n, bad, good, empty;
  vector<vector<vector<int> > > v;
  vector<bool> is_bad, is_good, is_empty;
  maintainer(int n) {
    this->n = n;
    bad = good = 0;
    empty = n;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      v[i].resize(2);
      for (int j = 0; j < 2; j++) v[i][j].resize(2);
    }
    is_bad.resize(n + 1, false);
    is_good.resize(n + 1, false);
    is_empty.resize(n + 1, true);
  }
  void add(int r, int c, int val) {
    c &= 1;
    if (is_empty[r]) {
      is_empty[r] = 0;
      empty--;
      is_good[r] = 1;
      good++;
    } else if (is_good[r]) {
      if (v[r][c][1 ^ val] > 0 || v[r][1 ^ c][val] > 0) {
        is_good[r] = 0;
        good--;
        is_bad[r] = 1;
        bad++;
      }
    }
    v[r][c][val]++;
  }
  void rem(int r, int c, int val) {
    c &= 1;
    if (v[r][0][0] + v[r][0][1] + v[r][1][0] + v[r][1][1] == 1) {
      is_good[r] = 0;
      good--;
      is_empty[r] = 1;
      empty++;
      v[r][c][val]--;
    } else if (is_bad[r]) {
      v[r][c][val]--;
      if ((v[r][0][0] == 0 || v[r][0][1] == 0) &&
          (v[r][1][0] == 0 || v[r][1][1] == 0) &&
          (v[r][0][0] == 0 || v[r][1][0] == 0) &&
          (v[r][0][1] == 0 || v[r][1][1] == 0)) {
        is_bad[r] = 0;
        bad--;
        is_good[r] = 1;
        good++;
      }
    } else
      v[r][c][val]--;
  }
  int get_empty_rows() {
    if (bad > 0) return -1;
    return empty;
  }
};
const long long N = 1e6 + 6, p = 998244353;
long long pw[N], n, m, k, x[2][2];
bool have_common() {
  if ((x[0][0] == 0 || x[0][1] == 0) && (x[1][0] == 0 || x[1][1] == 0) &&
      (x[0][0] == 0 || x[1][0] == 0) && (x[0][1] == 0 || x[1][1] == 0))
    return 1;
  return 0;
}
long long add(long long val1, long long val2) {
  long long res = val1 + val2;
  if (res >= p) res -= p;
  return res;
}
long long sub(long long val1, long long val2) {
  long long res = val1 - val2;
  if (res < 0) res += p;
  return res;
}
void func() {
  cin >> n >> m >> k;
  long long z = max(n, m);
  pw[0] = 1;
  for (long long i = 1; i < z + 1; i++) pw[i] = (pw[i - 1] * 2LL) % p;
  maintainer rows(n), columns(m);
  map<pair<long long, long long>, long long> mp;
  for (long long i = 1; i < k + 1; i++) {
    int r, c, val;
    cin >> r >> c >> val;
    map<pair<long long, long long>, long long>::iterator it =
        mp.find(make_pair(r, c));
    if (it != mp.end()) {
      long long org_val = it->second;
      if (val == -1) {
        rows.rem(r, c, org_val);
        columns.rem(c, r, org_val);
        x[(r + c) & 1][org_val]--;
        mp.erase(it);
      } else if (val != org_val) {
        rows.rem(r, c, org_val);
        columns.rem(c, r, org_val);
        x[(r + c) & 1][org_val]--;
        rows.add(r, c, val);
        columns.add(c, r, val);
        x[(r + c) & 1][val]++;
        it->second = val;
      }
    } else {
      if (val != -1) {
        rows.add(r, c, val);
        columns.add(c, r, val);
        x[(r + c) & 1][val]++;
        mp[make_pair(r, c)] = val;
      }
    }
    long long val1 = rows.get_empty_rows(), val2 = columns.get_empty_rows();
    if (val1 == -1 && val2 == -1)
      cout << "0\n";
    else if (val1 != -1 && val2 != -1) {
      if ((long long)mp.size() > 0) {
        if (have_common())
          cout << sub(add(pw[val1], pw[val2]), 1) << "\n";
        else
          cout << add(pw[val1], pw[val2]) << "\n";
      } else
        cout << sub(add(pw[val1], pw[val2]), 2) << "\n";
    } else if (val1 != -1)
      cout << pw[val1] << "\n";
    else if (val2 != -1)
      cout << pw[val2] << "\n";
  }
}
int main() {
  {
    ios ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  }
  cout << fixed << setprecision(8);
  long long ntc = 1;
  for (long long i = 1; i < ntc + 1; i++) {
    func();
  }
  return 0;
}

```