#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int Maxn = 1e6;
const long long P = 998244353LL;
int n, m, qn;
namespace Fread {
const int L = 1 << 15;
char buffer[L], *S, *T;
inline char Getchar() {
  if (S == T) {
    T = (S = buffer) + fread(buffer, 1, L, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
template <class T>
inline void read(T &X) {
  char ch;
  T op = 1;
  for (ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
    if (ch == '-') op = -1;
  for (X = 0; ch >= '0' && ch <= '9'; ch = Getchar())
    X = (X << 1) + (X << 3) + ch - '0';
  X *= op;
}
}  // namespace Fread
using Fread::read;
inline void inc(long long &x, long long y) {
  x += y;
  if (x >= P) x -= P;
}
inline void sub(long long &x, long long y) {
  x -= y;
  if (x < 0) x += P;
}
namespace Sub1 {
int s[2][2], cnt, con[2][2];
vector<vector<int>> ans;
inline void prework() {
  for (int a = 0; a < 2; a++)
    for (int b = 0; b < 2; b++)
      for (int c = 0; c < 2; c++)
        for (int d = 0; d < 2; d++)
          if (a + b + c + d == 2) {
            vector<int> cur = {a, b, c, d};
            ans.emplace_back(cur);
          }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) s[i][j] = -1;
}
inline bool chkSingle(int x, int y, int c) {
  assert(c != -1);
  if (s[x][y] == -1)
    return true;
  else
    return s[x][y] == c;
}
inline bool chk(int a, int b, int c, int d) {
  return chkSingle(0, 0, a) && chkSingle(0, 1, b) && chkSingle(1, 0, c) &&
         chkSingle(1, 1, d);
}
inline int calc() {
  if (cnt >= 1) return 0;
  int res = 0;
  for (int i = 0; i < ans.size(); i++) {
    if (chk(ans[i][0], ans[i][1], ans[i][2], ans[i][3])) ++res;
  }
  return res;
}
inline void solve() {
  prework();
  for (int x, y, c; qn--;) {
    read(x), read(y), read(c);
    --x, --y;
    s[x][y] = c;
    printf("%d\n", calc());
  }
}
}  // namespace Sub1
namespace Sub2 {
long long bin[N];
struct Counter {
  int len, conCnt, limCnt;
  set<int> s[N][2];
  inline int get(int x, int y) {
    set<int>::iterator it = s[y][0].find(x);
    if (it != s[y][0].end()) return 0;
    it = s[y][1].find(x);
    if (it != s[y][1].end()) return 1;
    return -1;
  }
  inline pair<int, int> state(int y) {
    if (s[y][0].empty() && s[y][1].empty())
      return pair<int, int>(0, 0);
    else if (!s[y][0].empty() && !s[y][1].empty())
      return pair<int, int>(0, 1);
    else
      return pair<int, int>(1, 0);
  }
  inline void ins(int x, int y, int c) {
    assert(get(x, y) == -1);
    assert(c != -1);
    if (!(x & 1)) c ^= 1;
    pair<int, int> st = state(y);
    limCnt -= st.first, conCnt -= st.second;
    s[y][c].insert(x);
    st = state(y);
    limCnt += st.first, conCnt += st.second;
  }
  inline void del(int x, int y) {
    int val = get(x, y);
    assert(val != -1);
    pair<int, int> st = state(y);
    limCnt -= st.first, conCnt -= st.second;
    s[y][val].erase(x);
    st = state(y);
    limCnt += st.first, conCnt += st.second;
  }
  inline void clear(int x, int y) {
    int v = get(x, y);
    if (v == -1) return;
    del(x, y);
  }
  inline void modify(int x, int y, int v) {
    if (v == -1)
      clear(x, y);
    else {
      int cur = get(x, y);
      if (cur != -1) del(x, y);
      ins(x, y, v);
    }
  }
  inline long long query() {
    if (conCnt >= 1)
      return 0LL;
    else
      return bin[len - limCnt];
  }
} c1, c2;
struct SlaCounter {
  const int len = 1;
  int conCnt, limCnt;
  set<pair<int, int>> s[2];
  inline int get(int x, int y) {
    set<pair<int, int>>::iterator it = s[0].find(pair<int, int>(x, y));
    if (it != s[0].end()) return 0;
    it = s[1].find(pair<int, int>(x, y));
    if (it != s[1].end()) return 1;
    return -1;
  }
  inline pair<int, int> state(int k) {
    assert(k >= 0 && k < 2);
    if (s[0].empty() && s[1].empty())
      return pair<int, int>(0, 0);
    else if (!s[0].empty() && !s[1].empty())
      return pair<int, int>(0, 1);
    else
      return pair<int, int>(1, 0);
  }
  inline void del(int x, int y) {
    int v = get(x, y);
    assert(v != -1);
    pair<int, int> st = state(v);
    limCnt -= st.first, conCnt -= st.second;
    s[v].erase(pair<int, int>(x, y));
    st = state(v);
    limCnt += st.first, conCnt += st.second;
  }
  inline void ins(int x, int y, int v) {
    assert(get(x, y) == -1);
    assert(v != -1);
    if ((x + y) & 1) v ^= 1;
    pair<int, int> st = state(v);
    limCnt -= st.first, conCnt -= st.second;
    s[v].insert(pair<int, int>(x, y));
    st = state(v);
    limCnt += st.first, conCnt += st.second;
  }
  inline void clear(int x, int y) {
    int v = get(x, y);
    if (v == -1) return;
    del(x, y);
  }
  inline void modify(int x, int y, int v) {
    if (v == -1)
      clear(x, y);
    else {
      if (get(x, y) != -1) del(x, y);
      ins(x, y, v);
    }
  }
  inline long long query() {
    if (conCnt >= 1)
      return 0LL;
    else
      return bin[len - limCnt];
  }
} cs;
inline void prework() {
  bin[0] = 1;
  for (int i = 1; i <= Maxn; i++) bin[i] = bin[i - 1] * 2LL % P;
}
inline void solve() {
  prework();
  c1.len = m, c2.len = n;
  for (int x, y, v; qn--;) {
    read(x), read(y), read(v);
    c1.modify(x, y, v);
    c2.modify(y, x, v);
    cs.modify(x, y, v);
    long long res = c1.query();
    inc(res, c2.query());
    sub(res, cs.query());
    printf("%lld\n", res);
  }
}
}  // namespace Sub2
int main() {
  read(n), read(m), read(qn);
  if (n == 2 && m == 2)
    Sub1::solve();
  else
    Sub2::solve();
  return 0;
}

### Prompt

Please formulate a cpp solution to 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;
const int N = 1e6 + 5;
const int Maxn = 1e6;
const long long P = 998244353LL;
int n, m, qn;
namespace Fread {
const int L = 1 << 15;
char buffer[L], *S, *T;
inline char Getchar() {
  if (S == T) {
    T = (S = buffer) + fread(buffer, 1, L, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
template <class T>
inline void read(T &X) {
  char ch;
  T op = 1;
  for (ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
    if (ch == '-') op = -1;
  for (X = 0; ch >= '0' && ch <= '9'; ch = Getchar())
    X = (X << 1) + (X << 3) + ch - '0';
  X *= op;
}
}  // namespace Fread
using Fread::read;
inline void inc(long long &x, long long y) {
  x += y;
  if (x >= P) x -= P;
}
inline void sub(long long &x, long long y) {
  x -= y;
  if (x < 0) x += P;
}
namespace Sub1 {
int s[2][2], cnt, con[2][2];
vector<vector<int>> ans;
inline void prework() {
  for (int a = 0; a < 2; a++)
    for (int b = 0; b < 2; b++)
      for (int c = 0; c < 2; c++)
        for (int d = 0; d < 2; d++)
          if (a + b + c + d == 2) {
            vector<int> cur = {a, b, c, d};
            ans.emplace_back(cur);
          }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) s[i][j] = -1;
}
inline bool chkSingle(int x, int y, int c) {
  assert(c != -1);
  if (s[x][y] == -1)
    return true;
  else
    return s[x][y] == c;
}
inline bool chk(int a, int b, int c, int d) {
  return chkSingle(0, 0, a) && chkSingle(0, 1, b) && chkSingle(1, 0, c) &&
         chkSingle(1, 1, d);
}
inline int calc() {
  if (cnt >= 1) return 0;
  int res = 0;
  for (int i = 0; i < ans.size(); i++) {
    if (chk(ans[i][0], ans[i][1], ans[i][2], ans[i][3])) ++res;
  }
  return res;
}
inline void solve() {
  prework();
  for (int x, y, c; qn--;) {
    read(x), read(y), read(c);
    --x, --y;
    s[x][y] = c;
    printf("%d\n", calc());
  }
}
}  // namespace Sub1
namespace Sub2 {
long long bin[N];
struct Counter {
  int len, conCnt, limCnt;
  set<int> s[N][2];
  inline int get(int x, int y) {
    set<int>::iterator it = s[y][0].find(x);
    if (it != s[y][0].end()) return 0;
    it = s[y][1].find(x);
    if (it != s[y][1].end()) return 1;
    return -1;
  }
  inline pair<int, int> state(int y) {
    if (s[y][0].empty() && s[y][1].empty())
      return pair<int, int>(0, 0);
    else if (!s[y][0].empty() && !s[y][1].empty())
      return pair<int, int>(0, 1);
    else
      return pair<int, int>(1, 0);
  }
  inline void ins(int x, int y, int c) {
    assert(get(x, y) == -1);
    assert(c != -1);
    if (!(x & 1)) c ^= 1;
    pair<int, int> st = state(y);
    limCnt -= st.first, conCnt -= st.second;
    s[y][c].insert(x);
    st = state(y);
    limCnt += st.first, conCnt += st.second;
  }
  inline void del(int x, int y) {
    int val = get(x, y);
    assert(val != -1);
    pair<int, int> st = state(y);
    limCnt -= st.first, conCnt -= st.second;
    s[y][val].erase(x);
    st = state(y);
    limCnt += st.first, conCnt += st.second;
  }
  inline void clear(int x, int y) {
    int v = get(x, y);
    if (v == -1) return;
    del(x, y);
  }
  inline void modify(int x, int y, int v) {
    if (v == -1)
      clear(x, y);
    else {
      int cur = get(x, y);
      if (cur != -1) del(x, y);
      ins(x, y, v);
    }
  }
  inline long long query() {
    if (conCnt >= 1)
      return 0LL;
    else
      return bin[len - limCnt];
  }
} c1, c2;
struct SlaCounter {
  const int len = 1;
  int conCnt, limCnt;
  set<pair<int, int>> s[2];
  inline int get(int x, int y) {
    set<pair<int, int>>::iterator it = s[0].find(pair<int, int>(x, y));
    if (it != s[0].end()) return 0;
    it = s[1].find(pair<int, int>(x, y));
    if (it != s[1].end()) return 1;
    return -1;
  }
  inline pair<int, int> state(int k) {
    assert(k >= 0 && k < 2);
    if (s[0].empty() && s[1].empty())
      return pair<int, int>(0, 0);
    else if (!s[0].empty() && !s[1].empty())
      return pair<int, int>(0, 1);
    else
      return pair<int, int>(1, 0);
  }
  inline void del(int x, int y) {
    int v = get(x, y);
    assert(v != -1);
    pair<int, int> st = state(v);
    limCnt -= st.first, conCnt -= st.second;
    s[v].erase(pair<int, int>(x, y));
    st = state(v);
    limCnt += st.first, conCnt += st.second;
  }
  inline void ins(int x, int y, int v) {
    assert(get(x, y) == -1);
    assert(v != -1);
    if ((x + y) & 1) v ^= 1;
    pair<int, int> st = state(v);
    limCnt -= st.first, conCnt -= st.second;
    s[v].insert(pair<int, int>(x, y));
    st = state(v);
    limCnt += st.first, conCnt += st.second;
  }
  inline void clear(int x, int y) {
    int v = get(x, y);
    if (v == -1) return;
    del(x, y);
  }
  inline void modify(int x, int y, int v) {
    if (v == -1)
      clear(x, y);
    else {
      if (get(x, y) != -1) del(x, y);
      ins(x, y, v);
    }
  }
  inline long long query() {
    if (conCnt >= 1)
      return 0LL;
    else
      return bin[len - limCnt];
  }
} cs;
inline void prework() {
  bin[0] = 1;
  for (int i = 1; i <= Maxn; i++) bin[i] = bin[i - 1] * 2LL % P;
}
inline void solve() {
  prework();
  c1.len = m, c2.len = n;
  for (int x, y, v; qn--;) {
    read(x), read(y), read(v);
    c1.modify(x, y, v);
    c2.modify(y, x, v);
    cs.modify(x, y, v);
    long long res = c1.query();
    inc(res, c2.query());
    sub(res, cs.query());
    printf("%lld\n", res);
  }
}
}  // namespace Sub2
int main() {
  read(n), read(m), read(qn);
  if (n == 2 && m == 2)
    Sub1::solve();
  else
    Sub2::solve();
  return 0;
}

```