题目背景

"我们永远不会忘记在这里的时光"

"再也没有其他地方能让我感到平静。谢谢。"

"很遗憾，Oshiro 先生，山庄要关门了。"

"我会赶上他们，直到这里的一切都井然有序……"

"在离开这个山庄之后，我应该去哪儿呢？"

题目描述

天空度假山庄是位于 Celeste 山半山腰上的一座山庄，这里已经被废弃许久。

当 Madeline 来到这座山庄之时，这里只剩下了一个幽灵，Oshiro 先生，独自管理这座山庄。

因为山庄有着神奇的魔力，里面凝聚着许多 Oshiro 先生不好的想法。

一个想法可能包含 $k$ 种不好的念头，诸如山庄倒闭，无人问津，无人体谅等等，每种念头对于 Oshiro 先生的重要度是不一样的，具体来讲，第 $i$ 种不好的念头对 Oshiro 先生的重要程度为 $2^{i-1}$。

有时，Oshiro 先生会抓起一堆糟糕的想法进行回忆，Oshiro 会一个一个挨着观看这些想法，并获得其中不好的念头。特别地，当 Oshiro 先生两次看到同一种不好的念头时，他就会认为这种念头没什么，下一瞬间就会忘记自己曾经看到过这种念头。

一次回忆对 Oshiro 先生的重要程度为 Oshiro 在看完这些想法之后记住的念头的重要程度和。

自然，在天空度假山庄里，Oshiro 先生对 Madeline 大吐苦水。

多年以后，当 Madeline 回忆她的登山之旅的时候，已经不记得 Oshiro 每个想法对于他的重要程度了，她只记得 Oshiro 先生的某几次回忆的重要程度以及天空度假山庄之中不好的想法的数量与每种想法中可能的不好的念头的数量。

你能帮助她找出有多少种合法的想法序列满足 Oshiro 先生的每次回忆吗？

特别地，一个想法也可能是一团浆糊，即里面什么都没有。

输入格式

第一行为三个整数 $n,q,k$，表示不好的想法的数量，Madeline 告诉了你 $q$ 条信息，以及每个想法中可能存在的不好的念头的数量。

接下来 $q$ 行，一行一条信息，首先是信息的类型 $op$。

若 $op = 0$， 则接下来是三个整数 $l,r,val$，表示 Madeline 想起在某次回忆中 Oshiro 先生抓起编号在 $[l,r]$ 区间的想法回忆，回忆结束后重要度是 $val$。

若 $op = 1$，则接下来是一个整数 $cnt$，表示 Madeline 纠正了第 $cnt$ 条 $op = 0$ 的说法，第 $cnt$ 条说法是她错误回忆起来的，保证第 $cnt$ 条说法存在并且没有被纠正过。(你可以认为，被纠正的说法就不再存在了)

若 $op = 2$，则你需要输出一个整数，表示有多少种合法的想法序列满足当前 Oshiro 先生的每次回忆，对 $998244353$ 取模。

输出格式

对于每次 $op = 2$，输出方案数，对 $998244353$ 取模。

4 3 2
0 3 4 1
0 2 3 3
2

16

8 9 6
0 1 1 1
0 2 2 9
0 3 3 2
0 4 4 6
0 5 5 0
0 6 6 8
0 7 7 1
0 8 8 7
2

1

10 15 14
2
0 6 6 439
0 3 8 1865
2
0 7 10 11371
2
1 1
2
2
1 3
2
0 5 8 7784
2
0 4 7 8497
2

155712307
76042715
719747106
76042715
76042715
74890016
76042715
719747106

提示

对于 $10\%$ 的数据, $n,k\leq 5,q \leq 15$

对于 $30\%$ 的数据, $n,q\leq 1000$

对于额外 $10\%$ 的数据, $k=1$

对于额外 $15\%$ 的数据，不存在1操作

对于 $75\%$ 的数据, $n\leq 30000,q\leq 80000,k \leq 20$

对于 $100\%$ 的数据, $ n\leq 2 * 10^5,q\leq 10^6,k\leq 30,0 \leq val < 2^k$