该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

特别地，对于 PyPy3 语言，时限 6000ms，但仍不建议使用 PyPy3 语言实现此题。

题目背景

一只羊正在修复一座不断出现裂隙的环形法阵。

法阵被等分成了 $M$ 个区域，按顺时针方向依次编号为 $1,2,\dots,M$。一只羊准备用 $N$ 种颜色给这些区域重新染色。

题目描述

共有 $N$ 种颜色，颜色编号为 $1,2,\dots,N$。

法阵上的相邻区域颜色必须不同。更具体地：

• 对于任意 $1\le i<M$，区域 $i$ 与区域 $i+1$ 相邻；

• 区域 $M$ 与区域 $1$ 也相邻。

初始时，所有区域都未被固定颜色，也就是说每个区域都可以自由选择任意一种颜色。

接下来会有 $Q$ 次操作，操作分为两种：

• 1 x c：将区域 $x$ 固定为颜色 $c$；

• 2 x：将区域 $x$ 取消固定，恢复为可以自由选择任意颜色。

如果某个区域已经被固定，那么再次执行 1 x c 表示将这个区域改为固定成新的颜色 $c$。

对于每次操作之后的当前状态，你都需要求出整个法阵的合法染色方案数。

特别地，本题中两种染色方案只要存在至少一个区域的颜色不同，就认为是不同方案；即使将整个法阵旋转后重合，它们仍然视为不同方案。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

第一行三个整数 $N,M,Q$，分别表示颜色种数、区域个数和操作次数。

接下来 $Q$ 行，每行描述一次操作。

如果这一行的第一个整数为 $1$，则接下来给出两个整数 $x,c$，表示将区域 $x$ 固定为颜色 $c$。

如果这一行的第一个整数为 $2$，则接下来给出一个整数 $x$，表示将区域 $x$ 取消固定。

输出格式

输出 $Q$ 行，每行一个整数，表示对应操作后当前合法染色方案数对 $998244353$ 取模后的结果。

3 4 6  
1 1 1  
1 3 1  
1 2 2  
1 4 2  
2 3  
2 2

6  
4  
2  
1  
2  
3

数据范围