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
import java.io.*;
import java.util.*;

public class Main{
    static int mod=998244353;
    static long[]pow2;
    static long hash(long x,long y){
        return x*1000001+y;
    }
    static int[][]rows,cols,cntRows,cntCols;
    static boolean[]validr,validc;
    static int cntr,cntc;
    static int notdecider,notdecidec;
    static boolean oddeven,evenodd;
    static void add(int x,int y,int val){
        if(rows[0][x]+rows[1][x]==0){
            notdecider--;
        }
        if(cols[0][y]+cols[1][y]==0){
            notdecidec--;
        }
        int parity=(y&1);
        if(val==0){
            parity^=1;
        }
        int parrow=(x&1);
        cntRows[parrow][parity]++;

        rows[parity][x]++;
        if(rows[parity^1][x]!=0){
            if(validr[x]){
                validr[x]=false;
                cntr--;
            }
        }

        parity=(x&1);
        if(val==0){
            parity^=1;
        }
        int parcol=(y&1);
        cntCols[parcol][parity]++;
        cols[parity][y]++;
        if(cols[parity^1][y]!=0){
            if(validc[y]){
                validc[y]=false;
                cntc--;
            }
        }
    }
    static void remove(int x,int y,int val){
        if(rows[0][x]+rows[1][x]==1){
            notdecider++;
        }
        if(cols[0][y]+cols[1][y]==1){
            notdecidec++;
        }
        int parity=(y&1);
        if(val==0){
            parity^=1;
        }
        int parrow=(x&1);
        cntRows[parrow][parity]--;
        rows[parity][x]--;
        if(rows[parity][x]==0){
            if(!validr[x]){
                validr[x]=true;
                cntr++;
            }
        }

        parity=(x&1);
        if(val==0){
            parity^=1;
        }
        int parcol=(y&1);
        cntCols[parcol][parity]--;
        cols[parity][y]--;
        if(cols[parity][y]==0){
            if(!validc[y]){
                validc[y]=true;
                cntc++;
            }
        }
    }
    static void main() throws Exception{
       int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
       rows=new int[2][n+1];cols=new int[2][m+1];
       validr=new boolean[n+1];validc=new boolean[m+1];
       cntRows=new int[2][2];
       cntCols=new int[2][2];
        for(int i=0;i<=n;i++)validr[i]=true;
        for(int i=0;i<=m;i++)validc[i]=true;
        HashMap<Long,Integer>val=new HashMap<>();
       cntr=n;cntc=m;
       notdecider=n;notdecidec=m;
        while(k-->0){
            int x=sc.nextInt(),y=sc.nextInt();
            int cmd=sc.nextInt();
            long hash=hash(x,y);
            if(val.containsKey(hash)){
                remove(x,y,val.get(hash));
                val.remove(hash);
            }
            if(cmd==-1){

            }
            else{
                add(x,y,cmd);
                val.put(hash,cmd);
            }

            oddeven=cntRows[1][0]==0 && cntRows[0][1]==0 && cntCols[1][0]==0 && cntCols[0][1]==0;
            evenodd=cntRows[1][1]==0 && cntRows[0][0]==0 && cntCols[1][1]==0 && cntCols[0][0]==0;
            int extra=(oddeven?1:0)+(evenodd?1:0);
            long ans=extra;
//            System.out.println(cntr+" "+cntc+" "+val);
            if(cntr==n){
                ans=(ans+pow2[notdecider]-extra+mod)%mod;
            }
            if(cntc==m){
                ans=(ans+pow2[notdecidec]-extra+mod)%mod;
            }
            ans=(ans+mod)%mod;
            pw.println(ans);
       }

	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
//		sc=new MScanner(" .in");
		pw = new PrintWriter(System.out);
		int tc=1;
        pow2=new long[1000001];
        pow2[0]=1;
        for(int i=1;i<pow2.length;i++){
            pow2[i]=(pow2[i-1]*2)%mod;
        }
//        tc=sc.nextInt();
		for(curt=1;curt<=tc;curt++) {
//			pw.printf("Case #%d: ", curt);
			main();
		}

		pw.flush();
	}
	static int curt;
	static PrintWriter pw;
	static MScanner sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
			return in;
		}
		public long[] longArr(int n) throws IOException {
			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
			return in;
		}
		public int[] intSortedArr(int n) throws IOException {
			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}
		public long[] longSortedArr(int n) throws IOException {
			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
			Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
			return in;
		}
		public Long[] LongArr(int n) throws IOException {
			Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
			return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}

	}
	static void dbg(int[]in) {
		System.out.println(Arrays.toString(in));
	}
	static void dbg(long[]in) {
		System.out.println(Arrays.toString(in));
	}
	static void sort(int[]in) {
		shuffle(in);
		Arrays.sort(in);
	}
	static void sort(long[]in) {
		shuffle(in);
		Arrays.sort(in);
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}