#include <bits/stdc++.h>
using namespace std;
mt19937 mr(time(0));
struct LL {
  static const long long int m = 998244353;
  long long int val;
  LL(long long int v) { val = reduce(v); };
  LL(int v) { val = reduce((long long int)v); };
  LL() { val = 0; };
  ~LL(){};
  LL(const LL& l) { val = l.val; };
  LL& operator=(int l) {
    val = l;
    return *this;
  }
  LL& operator=(long long int l) {
    val = l;
    return *this;
  }
  LL& operator=(LL l) {
    val = l.val;
    return *this;
  }
  static long long int reduce(long long int x, long long int md = m) {
    x %= md;
    while (x >= md) x -= md;
    while (x < 0) x += md;
    return x;
  }
  bool operator<(const LL& b) { return val < b.val; }
  bool operator<=(const LL& b) { return val <= b.val; }
  bool operator!=(const LL& b) { return val != b.val; }
  bool operator==(const LL& b) { return val == b.val; }
  bool operator>=(const LL& b) { return val >= b.val; }
  bool operator>(const LL& b) { return val > b.val; }
  LL operator+(const LL& b) { return LL(val + b.val); }
  LL operator+(const long long int& b) { return (*this + LL(b)); }
  LL& operator+=(const LL& b) { return (*this = *this + b); }
  LL& operator+=(const long long int& b) { return (*this = *this + b); }
  LL operator-(const LL& b) { return LL(val - b.val); }
  LL operator-(const long long int& b) { return (*this - LL(b)); }
  LL& operator-=(const LL& b) { return (*this = *this - b); }
  LL& operator-=(const long long int& b) { return (*this = *this - b); }
  LL operator*(const LL& b) { return LL(val * b.val); }
  LL operator*(const long long int& b) { return (*this * LL(b)); }
  LL& operator*=(const LL& b) { return (*this = *this * b); }
  LL& operator*=(const long long int& b) { return (*this = *this * b); }
  static LL exp(const LL& x, const long long int& y) {
    long long int z = y;
    z = reduce(z, m - 1);
    LL ret = 1;
    LL w = x;
    while (z) {
      if (z & 1) ret *= w;
      z >>= 1;
      w *= w;
    }
    return ret;
  }
  LL& operator^=(long long int y) { return (*this = LL(val ^ y)); }
  LL operator/(const LL& b) { return ((*this) * exp(b, -1)); }
  LL operator/(const long long int& b) { return (*this / LL(b)); }
  LL operator/=(const LL& b) { return ((*this) *= exp(b, -1)); }
  LL& operator/=(const long long int& b) { return (*this = *this / LL(b)); }
};
ostream& operator<<(ostream& os, const LL& obj) { return os << obj.val; }
using namespace std;
long long int cases, N, M, Q, K;
long long int rd() {
  long long int x;
  cin >> x;
  return x;
}
void fl() { cout.flush(); }
void panic(long long int out) {
  cout << out << endl;
  exit(0);
}
map<pair<int, int>, int> key;
int A[1000010 + 100010];
int X[1000010 + 100010];
LL PX = 1;
int X0 = 0;
int CX[1000010 + 100010][2];
int Y[1000010 + 100010];
LL PY = 1;
int Y0 = 0;
int CY[1000010 + 100010][2];
int B[2];
int ovr = 2;
void wash(int x, int y) {
  ovr = 2 - (B[0] > 0) - (B[1] > 0);
  if (X[x])
    PX /= X[x];
  else
    X0--;
  X[x] = 2 - (CX[x][0] > 0) - (CX[x][1] > 0);
  if (X[x])
    PX *= X[x];
  else
    X0++;
  if (Y[y])
    PY /= Y[y];
  else
    Y0--;
  Y[y] = 2 - (CY[y][0] > 0) - (CY[y][1] > 0);
  if (Y[y])
    PY *= Y[y];
  else
    Y0++;
}
void clr(int x, int y) {
  int md = (x + y + A[key[{x, y}]]) & 1;
  B[md]--;
  CX[x][md]--;
  CY[y][md]--;
  wash(x, y);
  A[key[{x, y}]] = -1;
}
void add(int x, int y, int top) {
  int md = (x + y + top) & 1;
  B[md]++;
  CX[x][md]++;
  CY[y][md]++;
  wash(x, y);
  A[key[{x, y}]] = top;
}
void read() {
  N = rd();
  M = rd();
  K = rd();
  Q = 0;
  for (int i = 0; i < N; ++i) {
    X[i] = 2;
    PX *= 2;
    CX[i][0] = CX[i][1] = 0;
  }
  for (int i = 0; i < M; ++i) {
    Y[i] = 2;
    PY *= 2;
    CY[i][0] = CY[i][1] = 0;
  }
  B[0] = 0;
  B[1] = 0;
  for (int q = 0; q < K; ++q) {
    int x = rd() - 1;
    int y = rd() - 1;
    int top = rd();
    if (key.find({x, y}) == key.end()) {
      key[{x, y}] = Q;
      A[Q++] = -1;
    }
    if (A[key[{x, y}]] != -1) clr(x, y);
    if (top >= 0) add(x, y, top);
    cout << (X0 ? 0 : PX) + (Y0 ? 0 : PY) - ovr << endl;
  }
}
int main() {
  bool trials = 0;
  bool interactive = 0;
  if (!interactive) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  }
  if (trials)
    cases = rd();
  else
    cases = 1;
  while (cases--) {
    read();
  }
}

### Prompt

In cpp, your task is to solve the following problem:

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;
mt19937 mr(time(0));
struct LL {
  static const long long int m = 998244353;
  long long int val;
  LL(long long int v) { val = reduce(v); };
  LL(int v) { val = reduce((long long int)v); };
  LL() { val = 0; };
  ~LL(){};
  LL(const LL& l) { val = l.val; };
  LL& operator=(int l) {
    val = l;
    return *this;
  }
  LL& operator=(long long int l) {
    val = l;
    return *this;
  }
  LL& operator=(LL l) {
    val = l.val;
    return *this;
  }
  static long long int reduce(long long int x, long long int md = m) {
    x %= md;
    while (x >= md) x -= md;
    while (x < 0) x += md;
    return x;
  }
  bool operator<(const LL& b) { return val < b.val; }
  bool operator<=(const LL& b) { return val <= b.val; }
  bool operator!=(const LL& b) { return val != b.val; }
  bool operator==(const LL& b) { return val == b.val; }
  bool operator>=(const LL& b) { return val >= b.val; }
  bool operator>(const LL& b) { return val > b.val; }
  LL operator+(const LL& b) { return LL(val + b.val); }
  LL operator+(const long long int& b) { return (*this + LL(b)); }
  LL& operator+=(const LL& b) { return (*this = *this + b); }
  LL& operator+=(const long long int& b) { return (*this = *this + b); }
  LL operator-(const LL& b) { return LL(val - b.val); }
  LL operator-(const long long int& b) { return (*this - LL(b)); }
  LL& operator-=(const LL& b) { return (*this = *this - b); }
  LL& operator-=(const long long int& b) { return (*this = *this - b); }
  LL operator*(const LL& b) { return LL(val * b.val); }
  LL operator*(const long long int& b) { return (*this * LL(b)); }
  LL& operator*=(const LL& b) { return (*this = *this * b); }
  LL& operator*=(const long long int& b) { return (*this = *this * b); }
  static LL exp(const LL& x, const long long int& y) {
    long long int z = y;
    z = reduce(z, m - 1);
    LL ret = 1;
    LL w = x;
    while (z) {
      if (z & 1) ret *= w;
      z >>= 1;
      w *= w;
    }
    return ret;
  }
  LL& operator^=(long long int y) { return (*this = LL(val ^ y)); }
  LL operator/(const LL& b) { return ((*this) * exp(b, -1)); }
  LL operator/(const long long int& b) { return (*this / LL(b)); }
  LL operator/=(const LL& b) { return ((*this) *= exp(b, -1)); }
  LL& operator/=(const long long int& b) { return (*this = *this / LL(b)); }
};
ostream& operator<<(ostream& os, const LL& obj) { return os << obj.val; }
using namespace std;
long long int cases, N, M, Q, K;
long long int rd() {
  long long int x;
  cin >> x;
  return x;
}
void fl() { cout.flush(); }
void panic(long long int out) {
  cout << out << endl;
  exit(0);
}
map<pair<int, int>, int> key;
int A[1000010 + 100010];
int X[1000010 + 100010];
LL PX = 1;
int X0 = 0;
int CX[1000010 + 100010][2];
int Y[1000010 + 100010];
LL PY = 1;
int Y0 = 0;
int CY[1000010 + 100010][2];
int B[2];
int ovr = 2;
void wash(int x, int y) {
  ovr = 2 - (B[0] > 0) - (B[1] > 0);
  if (X[x])
    PX /= X[x];
  else
    X0--;
  X[x] = 2 - (CX[x][0] > 0) - (CX[x][1] > 0);
  if (X[x])
    PX *= X[x];
  else
    X0++;
  if (Y[y])
    PY /= Y[y];
  else
    Y0--;
  Y[y] = 2 - (CY[y][0] > 0) - (CY[y][1] > 0);
  if (Y[y])
    PY *= Y[y];
  else
    Y0++;
}
void clr(int x, int y) {
  int md = (x + y + A[key[{x, y}]]) & 1;
  B[md]--;
  CX[x][md]--;
  CY[y][md]--;
  wash(x, y);
  A[key[{x, y}]] = -1;
}
void add(int x, int y, int top) {
  int md = (x + y + top) & 1;
  B[md]++;
  CX[x][md]++;
  CY[y][md]++;
  wash(x, y);
  A[key[{x, y}]] = top;
}
void read() {
  N = rd();
  M = rd();
  K = rd();
  Q = 0;
  for (int i = 0; i < N; ++i) {
    X[i] = 2;
    PX *= 2;
    CX[i][0] = CX[i][1] = 0;
  }
  for (int i = 0; i < M; ++i) {
    Y[i] = 2;
    PY *= 2;
    CY[i][0] = CY[i][1] = 0;
  }
  B[0] = 0;
  B[1] = 0;
  for (int q = 0; q < K; ++q) {
    int x = rd() - 1;
    int y = rd() - 1;
    int top = rd();
    if (key.find({x, y}) == key.end()) {
      key[{x, y}] = Q;
      A[Q++] = -1;
    }
    if (A[key[{x, y}]] != -1) clr(x, y);
    if (top >= 0) add(x, y, top);
    cout << (X0 ? 0 : PX) + (Y0 ? 0 : PY) - ovr << endl;
  }
}
int main() {
  bool trials = 0;
  bool interactive = 0;
  if (!interactive) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  }
  if (trials)
    cases = rd();
  else
    cases = 1;
  while (cases--) {
    read();
  }
}

```