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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#include <chrono>

#define int long long
#define ld long double
#define db double
#define endl "\n"
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace __gnu_pbds; 
using namespace std;
using namespace chrono;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void deb_out() { 
    cout << endl; 
}
template <typename Head, typename... Tail>
void deb_out(Head H, Tail... T) {
    cout << " " << H;
    deb_out(T...);
}
#ifdef LOCAL
    #define deb(...) cout << "[" << #__VA_ARGS__ << "]:", deb_out(__VA_ARGS__);
#else
    #define deb(...) ;
#endif

const long double PI = 3.14159265358979323846264338;
const long long INF = 1000000000000000000;
const long long INF1 = 1000000000;
// const long long MOD = 1000000007;
const long long MOD = 998244353;

inline int cl(int a, int b){
    if(a % b)
        return 1 + a / b;
    return a / b;
}
        
int mpow(int a, int b){
    a %= MOD;
    if(!b)
        return 1;
    int temp = mpow(a, b / 2);
    temp = (temp * temp) % MOD;
    if(b % 2)
        return (a * temp) % MOD;
    return temp;
}
int _pow(int a, int b){
    if(!b)
        return 1;
    int temp = _pow(a, b / 2);
    temp = (temp * temp);
    if(b % 2)
        return (a * temp);
    return temp;
}
inline int mod_in(int n){
    return mpow(n, MOD - 2);
}

void remove(int x, int y, int row[][2], int col[][2], int val, int r[], int c[], int poss[]) {
    int ux = y % 2, uy = x % 2;
    int vx = 1 - ux, vy = 1 - uy;   
    if (val == 1) {
        row[x][ux]--;
        col[y][uy]--;
        if (row[x][1] == 0 && row[x][0] == 0) {
            r[2]++;
            r[1]--;
        }
        if (row[x][ux] == 0 && row[x][vx]) {
            r[1]++;
            r[0]--;
        }
        if (col[y][1] == 0 && col[y][0] == 0) {
            c[2]++;
            c[1]--;
        }
        if (col[y][uy] == 0 && col[y][vy]) {
            c[1]++;
            c[0]--;
        }
        int parity = (ux + uy) % 2;
        if (parity == 0) {
            poss[0]--;
        } else {
            poss[1]--;
        }
    } else {
        row[x][vx]--;
        col[y][vy]--;
        if (row[x][1] == 0 && row[x][0] == 0) {
            r[2]++;
            r[1]--;
        }
        if (row[x][vx] == 0 && row[x][ux]) {
            r[1]++;
            r[0]--;
        }
        if (col[y][1] == 0 && col[y][0] == 0) {
            c[2]++;
            c[1]--;
        }
        if (col[y][vy] == 0 && col[y][uy]) {
            c[1]++;
            c[0]--;
        }
        int parity = (ux + uy) % 2;
        if (parity == 1) {
            poss[0]--;
        } else {
            poss[1]--;
        }
    }
}

// 1 #
// # #

// 1 1
// # #

// 1 1
// 1 #

// 0 1
// 1 #

// 0 #
// 1 #

const int N = 1e6 + 6;
int row[N][2], col[N][2];   


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int Tests = 1;
    // cin >> Tests;
    while (Tests--) {
        int n, m, k;
        cin >> n >> m >> k;
        map<pair<int, int>, int> M;
        int r[3], c[3];
        r[0] = 0;
        c[0] = 0;
        r[2] = n;
        r[1] = 0;
        c[2] = m;
        c[1] = 0;
        int fix = 0;
        int poss[2] = {0};
        while (k--) {
            int x, y, t;
            cin >> x >> y >> t;
            x--;
            y--;
            int ux = y % 2, uy = x % 2;
            int vx = 1 - ux, vy = 1 - uy;
            int parity = (ux + uy) % 2;
            deb(r[1], r[2], c[1], c[2])
            if (t == 1) {
                if (M.find({x, y}) != M.end() && M[{x, y}] != -1) {
                    remove(x, y, row, col, M[{x, y}], r, c, poss);
                    fix--;
                }
                M[{x, y}] = 1;
                fix++;
                row[x][ux]++;
                col[y][uy]++;
                if (row[x][ux] == 1 && row[x][vx]) {
                    r[0]++;
                    r[1]--;
                }
                if (row[x][ux] == 1 && row[x][vx] == 0) {
                    r[2]--;
                    r[1]++;
                }
                if (col[y][uy] == 1 && col[y][vy]) {
                    c[0]++;
                    c[1]--;
                }
                if (col[y][uy] == 1 && col[y][vy] == 0) {
                    c[2]--;
                    c[1]++;
                }
                if (parity == 0) {
                    poss[0]++;
                } else {
                    poss[1]++;
                }
                deb(x, ux, vx, row[x][0], row[x][1])
            } else if (t == 0) {
                if (M.find({x, y}) != M.end() && M[{x, y}] != -1) {
                    remove(x, y, row, col, M[{x, y}], r, c, poss);
                    fix--;
                }
                M[{x, y}] = 0;
                fix++;
                row[x][vx]++;
                col[y][vy]++;
                if (row[x][vx] == 1 && row[x][ux]) {
                    r[0]++;
                    r[1]--;
                }
                if (row[x][vx] == 1 && row[x][ux] == 0) {
                    r[2]--;
                    r[1]++;
                }
                if (col[y][vy] == 1 && col[y][uy]) {
                    c[0]++;
                    c[1]--;
                }
                if (col[y][vy] == 1 && col[y][uy] == 0) {
                    c[2]--;
                    c[1]++;
                }
                if (parity == 1) {
                    poss[0]++;
                } else {
                    poss[1]++;
                }
            } else {
                remove(x, y, row, col, M[{x, y}], r, c, poss);
                M[{x, y}] = -1;
            }
            deb(r[0], r[1], r[2], c[0], c[1], c[2])
            int ans1 = mpow(2, r[2]) * ((r[1] + r[2] == n));
            int ans2 = mpow(2, c[2]) * ((c[1] + c[2] == m));
            deb(ans1, ans2, poss[0], poss[1])
            cout << (ans1 + ans2 - (poss[0] == 0) - (poss[1] == 0) + MOD) % MOD << endl;

        }
    }
}
