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

Difficulty: VERY_HARD
Tags: Mathematics

Combinatorics

Implementation

Constructive algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
p = 998244353

class matrix_data:

	def __init__(self, n, m):
		self.n = n
		self.m = m
		self.filled = {}
		self.alternating = [0, 0]
		self.rows = [[0] * (n + 1), [0] * (n + 1)]
		self.cols = [[0] * (m + 1), [0] * (m + 1)]
		self.frozen_rows = 0
		self.frozen_cols = 0
		self.bad_rows = 0
		self.bad_cols = 0

	def clear(self, x, y):
		if (x, y) not in self.filled:
			return
		t = self.filled.pop((x, y))
		self.alternating[(x + y + t) % 2] -= 1
		self.rows[(y + t) % 2][x] -= 1
		if self.rows[(y + t) % 2][x] == 0:
			if self.rows[(y + t + 1) % 2][x] == 0:
				self.frozen_rows -= 1
			else:
				self.bad_rows -= 1
		self.cols[(x + t) % 2][y] -= 1
		if self.cols[(x + t) % 2][y] == 0:
			if self.cols[(x + t + 1) % 2][y] == 0:
				self.frozen_cols -= 1
			else:
				self.bad_cols -= 1

	def write(self, x, y, t):
		self.filled[x, y] = t
		self.alternating[(x + y + t) % 2] += 1
		self.rows[(y + t) % 2][x] += 1
		if self.rows[(y + t) % 2][x] == 1:
			if self.rows[(y + t + 1) % 2][x] == 0:
				self.frozen_rows += 1
			else:
				self.bad_rows += 1
		self.cols[(x + t) % 2][y] += 1
		if self.cols[(x + t) % 2][y] == 1:
			if self.cols[(x + t + 1) % 2][y] == 0:
				self.frozen_cols += 1
			else:
				self.bad_cols += 1

	def count(self):
		total = 0
		if self.bad_rows == 0:
			total += pow(2, n - self.frozen_rows, p)
		if self.bad_cols == 0:
			total += pow(2, m - self.frozen_cols, p)
		if self.alternating[0] == 0:
			total -= 1
		if self.alternating[1] == 0:
			total -= 1
		print(total % p)
(n, m, k) = map(int, input().split())
data = matrix_data(n, m)
for _ in range(k):
	(x, y, t) = map(int, input().split())
	if t == -1:
		data.clear(x, y)
	else:
		data.clear(x, y)
		data.write(x, y, t)
	data.count()


import sys
input = sys.stdin.buffer.readline
(n, m, q) = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(q)]
MOD = 998244353
pow2 = [0] * (10 ** 6 + 10 + 1)
pow2[0] = 1
for i in range(10 ** 6 + 10):
	pow2[i + 1] = pow2[i] * 2 % MOD
ans = [0] * q
cnt0 = [0] * n
cnt1 = [0] * n
mass = {}
none = n
zero = 0
one = 0
invalid = 0
for (idx, (i, j, flag)) in enumerate(queries):
	i -= 1
	j -= 1
	if (i, j) in mass:
		(c0, c1) = (cnt0[i], cnt1[i])
		if mass[i, j] == 0 and j % 2 == 0:
			cnt0[i] -= 1
		if mass[i, j] == 0 and j % 2 == 1:
			cnt1[i] -= 1
		if mass[i, j] == 1 and j % 2 == 0:
			cnt1[i] -= 1
		if mass[i, j] == 1 and j % 2 == 1:
			cnt0[i] -= 1
		del mass[i, j]
		if c0 == 1 and cnt0[i] == 0 and (cnt1[i] == 0):
			zero -= 1
			none += 1
		if c1 == 1 and cnt1[i] == 0 and (cnt0[i] == 0):
			one -= 1
			none += 1
		if c0 == 1 and cnt0[i] == 0 and (cnt1[i] > 0):
			invalid -= 1
			one += 1
		if c1 == 1 and cnt1[i] == 0 and (cnt0[i] > 0):
			invalid -= 1
			zero += 1
	(c0, c1) = (cnt0[i], cnt1[i])
	if flag == 0 and j % 2 == 0:
		mass[i, j] = 0
		cnt0[i] += 1
	if flag == 0 and j % 2 == 1:
		mass[i, j] = 0
		cnt1[i] += 1
	if flag == 1 and j % 2 == 0:
		mass[i, j] = 1
		cnt1[i] += 1
	if flag == 1 and j % 2 == 1:
		mass[i, j] = 1
		cnt0[i] += 1
	if c0 == 0 and c1 == 0 and (cnt0[i] == 1):
		zero += 1
		none -= 1
	if c0 == 0 and c1 == 0 and (cnt1[i] == 1):
		one += 1
		none -= 1
	if c0 == 0 and cnt0[i] > 0 and (cnt1[i] > 0):
		invalid += 1
		one -= 1
	if c1 == 0 and cnt0[i] > 0 and (cnt1[i] > 0):
		invalid += 1
		zero -= 1
	if invalid > 0:
		continue
	ans[idx] += pow2[none]
	ans[idx] %= MOD
cnt0 = [0] * m
cnt1 = [0] * m
mass = {}
none = m
zero = 0
one = 0
invalid = 0
for (idx, (i, j, flag)) in enumerate(queries):
	(i, j) = (j, i)
	i -= 1
	j -= 1
	if (i, j) in mass:
		(c0, c1) = (cnt0[i], cnt1[i])
		if mass[i, j] == 0 and j % 2 == 0:
			cnt0[i] -= 1
		if mass[i, j] == 0 and j % 2 == 1:
			cnt1[i] -= 1
		if mass[i, j] == 1 and j % 2 == 0:
			cnt1[i] -= 1
		if mass[i, j] == 1 and j % 2 == 1:
			cnt0[i] -= 1
		del mass[i, j]
		if c0 == 1 and cnt0[i] == 0 and (cnt1[i] == 0):
			zero -= 1
			none += 1
		if c1 == 1 and cnt1[i] == 0 and (cnt0[i] == 0):
			one -= 1
			none += 1
		if c0 == 1 and cnt0[i] == 0 and (cnt1[i] > 0):
			invalid -= 1
			one += 1
		if c1 == 1 and cnt1[i] == 0 and (cnt0[i] > 0):
			invalid -= 1
			zero += 1
	(c0, c1) = (cnt0[i], cnt1[i])
	if flag == 0 and j % 2 == 0:
		mass[i, j] = 0
		cnt0[i] += 1
	if flag == 0 and j % 2 == 1:
		mass[i, j] = 0
		cnt1[i] += 1
	if flag == 1 and j % 2 == 0:
		mass[i, j] = 1
		cnt1[i] += 1
	if flag == 1 and j % 2 == 1:
		mass[i, j] = 1
		cnt0[i] += 1
	if c0 == 0 and c1 == 0 and (cnt0[i] == 1):
		zero += 1
		none -= 1
	if c0 == 0 and c1 == 0 and (cnt1[i] == 1):
		one += 1
		none -= 1
	if c0 == 0 and cnt0[i] > 0 and (cnt1[i] > 0):
		invalid += 1
		one -= 1
	if c1 == 0 and cnt0[i] > 0 and (cnt1[i] > 0):
		invalid += 1
		zero -= 1
	if invalid > 0:
		continue
	ans[idx] += pow2[none]
	ans[idx] %= MOD
even = [0, 0]
odd = [0, 0]
mass = {}
for (idx, (i, j, flag)) in enumerate(queries):
	if (i, j) in mass:
		if (i + j) % 2 == 0:
			even[mass[i, j]] -= 1
		else:
			odd[mass[i, j]] -= 1
		del mass[i, j]
	if flag == 0 or flag == 1:
		mass[i, j] = flag
		if (i + j) % 2 == 0:
			even[flag] += 1
		else:
			odd[flag] += 1
	if sum(even) + sum(odd) == 0:
		ans[idx] -= 2
		ans[idx] %= MOD
	elif even[0] * even[1] > 0 or odd[0] * odd[1] > 0 or even[0] * odd[0] > 0 or (even[1] * odd[1] > 0):
		pass
	else:
		ans[idx] -= 1
		ans[idx] %= MOD
print('\n'.join(map(str, ans)))


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, k) = map(int, input().split())
mod = 998244353
MOD22 = [[0, 0], [0, 0]]
R = [[0] * n, [0] * n]
C = [[0] * m, [0] * m]
RB = 0
CB = 0
RK = 0
CK = 0
D = dict()
ANSLIST = []
POW2 = [1]
for i in range(10 ** 6 + 4):
	POW2.append(POW2[-1] * 2 % mod)
for i in range(k):
	(x, y, t) = map(int, input().split())
	x -= 1
	y -= 1
	if t != -1:
		if (x, y) in D:
			if D[x, y] == t:
				True
			else:
				D[x, y] = t
				k = (y + t) % 2
				if R[0][x] > 0 and R[1][x] > 0:
					RBini = 1
				else:
					RBini = 0
				R[k][x] += 1
				R[1 - k][x] -= 1
				if R[0][x] > 0 and R[1][x] > 0:
					RBnow = 1
				else:
					RBnow = 0
				RB += RBnow - RBini
				k = (x + t) % 2
				if C[0][y] > 0 and C[1][y] > 0:
					CBini = 1
				else:
					CBini = 0
				C[k][y] += 1
				C[1 - k][y] -= 1
				if C[0][y] > 0 and C[1][y] > 0:
					CBnow = 1
				else:
					CBnow = 0
				CB += CBnow - CBini
				MOD22[t][(x + y) % 2] += 1
				MOD22[1 - t][(x + y) % 2] -= 1
		else:
			if R[0][x] > 0 and R[1][x] > 0:
				RBini = 1
			else:
				RBini = 0
			if C[0][y] > 0 and C[1][y] > 0:
				CBini = 1
			else:
				CBini = 0
			D[x, y] = t
			k = (y + t) % 2
			R[k][x] += 1
			if R[k][x] + R[1 - k][x] == 1:
				RK += 1
			k = (x + t) % 2
			C[k][y] += 1
			if R[0][x] > 0 and R[1][x] > 0:
				RBnow = 1
			else:
				RBnow = 0
			RB += RBnow - RBini
			if C[k][y] + C[1 - k][y] == 1:
				CK += 1
			if C[0][y] > 0 and C[1][y] > 0:
				CBnow = 1
			else:
				CBnow = 0
			CB += CBnow - CBini
			MOD22[t][(x + y) % 2] += 1
	elif (x, y) in D:
		t = D[x, y]
		k = (y + t) % 2
		if R[0][x] > 0 and R[1][x] > 0:
			RBini = 1
		else:
			RBini = 0
		R[k][x] -= 1
		if R[k][x] + R[1 - k][x] == 0:
			RK -= 1
		if R[0][x] > 0 and R[1][x] > 0:
			RBnow = 1
		else:
			RBnow = 0
		RB += RBnow - RBini
		k = (x + t) % 2
		if C[0][y] > 0 and C[1][y] > 0:
			CBini = 1
		else:
			CBini = 0
		C[k][y] -= 1
		if C[k][y] + C[1 - k][y] == 0:
			CK -= 1
		if C[0][y] > 0 and C[1][y] > 0:
			CBnow = 1
		else:
			CBnow = 0
		CB += CBnow - CBini
		MOD22[t][(x + y) % 2] -= 1
		del D[x, y]
	else:
		True
	ANS = 0
	if RB == 0:
		ANS += POW2[n - RK]
	if CB == 0:
		ANS += POW2[m - CK]
	if MOD22[0][0] == 0 and MOD22[1][1] == 0:
		ANS -= 1
	if MOD22[1][0] == 0 and MOD22[0][1] == 0:
		ANS -= 1
	ANSLIST.append(str(ANS % mod))
sys.stdout.write('\n'.join(ANSLIST))