Painting Fences
题号：NC232413
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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

定义 为一个极长颜色连续段，当且仅当同时满足：

- 第 个格子内的颜色相同；
- 或 ；
- 或 。

你会随机粉刷每一个栅栏的格子（即，对于每个格子，等概率随机染它目前可以染的颜色）。你想知道极长颜色连续段个数的期望对 998244353 取模的值。

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

输入描述:

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

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

- `1 x y` 加入限制「a_x 不能是 y」。保证这次操作之前，a_x 可以是 y。
- `2 id` 取消第 id 个操作的限制（下标从 1 开始，取消的操作保证是第一种类型的操作）。

对于所有数据，，，，保证任意时刻至少有一种合法方案。

输出描述:

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

输入

复制 
4 2 5
1 2 1
1 1 1
1 3 2
2 2
1 4 2

输出

复制 
499122179
499122179
2
499122179
3
499122179

说明

- 在所有操作之前的方案：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}。