本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-09-30 09:48:10

D:

bfs,用优先队列，从最大值状态开始换小一个数的，如果遇到一个非m的状态，就是所求答案。

E:

\/\/TJ
\/\/要么行异色，要么列异色 
#include<bits\/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
int n,m,k,pw[N],cx[N][2],cy[N][2],c[2],c1,c2;\/\/cx,分奇数列和偶数列 
map<pair<int,int>,bool>mp;
inline void work(int x,int y,int v)
{
	if(!cx[x][0]&&!cx[x][1])n+=v;\/\/* cx，cx[x][0]描述x行的奇数列填1或偶数列填0的情况。cx[x][1]代表奇数列填0，没填0和1，那么这个位置就随便填。 
	if(!cy[y][0]&&!cy[y][1])m+=v;\/\/* cy，代表行随便填的情况。 
	if(cx[x][0]&&cx[x][1])c1+=v;\/\/矛盾，例如奇数列了1，偶数列也填了1，这样就不是每列不同了，产生矛盾
	if(cy[y][0]&&cy[y][1])c2+=v;\/\/如果奇数行填1，偶数行也填1，又产生矛盾 
\/\/	cout<<"cx: "<<x<<":"<<cx[x][0]<<" "<<cx[x][1]<<"  cy"<<y<<":"<<cy[y][0]<<" "<<cy[y][1]<<endl; 
\/\/	cout<<"  nm "<<n<<" "<<m<<" c1,c2:"<<c1<<" "<<c2<<endl;
}
\/*
del 
例如：描述行相异的情况，
如果多个列内有数据，
	对n，m第一个work不会起作用。第二个也不会。
	对c1c2，删除会减少矛盾，先减去，如果矛盾存在，就继续加上。
只有当对唯一有数据的列操作时候-1无用，+1有用，增加一个* 	 
*\/ 
inline void del(int x,int y,bool t)
{
	work(x,y,-1);\/\/原来的 **1*、****，原来的这个1要删去符合条件才减去 
	--cx[x][(y&1)^t];\/\/单点修改。 
	--cy[y][(x&1)^t];
	--c[(abs(x-y)&1)^t];
	work(x,y,1);
}
\/*
ins 
例如：描述行相异的情况，
如果多个列内有数据，
	对n，m第一个work不会起作用。第二个也不会。 
	对c1c2，如果原来没矛盾，-1不会起作用。增加后，+1才可能起作用。 
只有当第一次变成有数的时候：-1有用，+1无用，减少一个*
*\/ 
inline void ins(int x,int y,bool t)
{
	work(x,y,-1);
	++cx[x][(y&1)^t];\/\/x行，若1^1和0^0在奇数列填1和在偶数列填0的效果一样，奇数列填1相当于这一列需要的0个数增加了 
					\/\/奇数列有1相当于偶数列有0；奇数列有0相当于偶数列有1 ，
					\/\/cx[x][0]统计的是奇数列 填1或偶数列填0的个数 ;cx[x][1]记录奇数填0或偶数列填1的个数。 
	++cy[y][(x&1)^t];
	++c[(abs(x-y)&1)^t];\/\/ 描述左右45度线的奇偶性 ，a11填1和a12填0,a22填1，a21填0都是c[1],   
	\/*
	 c[0]	01   c[1] 10
		    10        01  这种情况行也不同，列也不同，会重复统计 
	*\/ 
	work(x,y,1);
}
inline void print()
{
	int ans=add(c1?0:pw[n],c2?0:pw[m]);\/\/如果c1非零，说明列有矛盾，不能列不同的方式填充！c2同理 
	\/\/ 如果没有c[0],那就要在行不同里面减去列不同的情况，c[1]同理。 
	ans=dec(ans,(c[0]==0)+(c[1]==0));
	printf("%d\n",ans);
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	pw[0]=1;for(int i=1;i<=max(n,m);++i)pw[i]=add(pw[i-1],pw[i-1]);\/\/无限制 2^i 
	while(k--)
	{
		int x,y,t;scanf("%d%d%d",&x,&y,&t);
		auto now=make_pair(x,y);
		if(mp.count(now))\/\/如果存在，先删掉 
		{
			del(x,y,mp[now]);\/\/删掉原来的0或者1 
			mp.erase(now);
		}
		if(t>=0)ins(x,y,t),mp[now]=t;\/\/改成需要的0或者1. 
		print();
	}
	return 0;
}