题目描述

你要粉刷一段墙壁。墙壁的长度为 $n$，分为 $n$ 段长度为 $1$ 的格子，编号为 $1\sim n$。每一个格子被粉刷颜色必须相同。共有 $m$ 种颜色，编号为 $1\sim m$。设第 $i$ 个格子内刷颜色 $a_i$。

定义 $[l,r]$ 为一个极长颜色连续段，当且仅当同时满足：

• 第 $i (i\in [l,r])$ 个格子内的颜色相同；
• $l=1$ 或 $a_l\ne a_{l-1}$；
• $r=n$ 或 $a_r\ne a_{r+1}$。

你会随机粉刷每一段栅栏。你想知道极长颜色连续段个数的期望对 $998244353$ 取模的值。

可难满足的栅栏主人提出了一些要求。有 $q$ 次操作，每次加入一条限制「$a_x$ 不能是 $y$」，或删除一条限制。你需要在每次操作后求出答案。

输入格式

第一行是三个正整数 $n,m,q$。

接下来 $q$ 行，每行为以下两种：

• 1 x y 加入限制「$a_x$ 不能是 $y$」。
• 2 id 取消第 $id$ 个操作的限制（下标从 $1$ 开始，保证这次操作是操作 $1$）。

输出格式

$q+1$ 行，对初始状态、每个操作后的状态分别输出答案对 $998244353$ 取模的值。

样例

样例输入 1

4 2 5
1 2 1
1 1 1
1 3 2
2 2
1 4 2

样例输出 1

499122179
499122179
2
499122179
3
499122179

样例 1 解释

• 在所有操作之前的方案：$1111,1112,1121,1122,1211,1212,1221,1222,2111,2112,2121,2122,2211,2212,2221,2222$，答案等于 $\dfrac{2\times 1+6\times 2+6\times 3+2\times 4}{16}=\dfrac{5}{2}$。
• 在第一次操作之后的方案：$1211,1212,1221,1222,2211,2212,2221,2222$，答案等于 $\dfrac{1\times 1+3\times 2+3\times 3+1\times 4}{8}=\dfrac{5}{2}$。
• 在第二次操作之后的方案：$2211,2212,2221,2222$，答案等于 $\dfrac{1\times 1+2\times 2+1\times 3}{4}=2$。
• 在第三次操作之后的方案：$2211,2212$，答案等于 $\dfrac{1\times 2+1\times 3}{2}=\dfrac{5}{2}$。
• 在第四次操作之后的方案：$1211,1212,2211,2212$，答案等于 $\dfrac{1\times 2+2\times 3+1\times 4}{4}=3$。
• 在第五次操作之后的方案：$1211,2211$，答案等于 $\dfrac{1\times 2+1\times 3}{2}=\dfrac{5}{2}$。

数据范围

本题捆绑测试。

对于所有数据，$1\le n\le 2\times 10^5$，$1\le q\le 3\times 10^5$，$2\le m<998244353$，保证操作合法，且任意时刻至少有一种合法方案。详细数据范围如下表。