Description

The Celestial Resort is a resort located halfway up Celeste Mountain, and it has been abandoned for a long time.

When Madeline arrives at the resort, there is only one ghost left, Mr. Oshiro, managing it alone.

Because the resort has some magical power, it gathers many of Mr. Oshiro’s bad thoughts.

A thought may contain $k$ kinds of bad ideas, such as the resort shutting down, nobody visiting, nobody understanding him, and so on. The importance of each kind of bad idea to Mr. Oshiro is different. Specifically, the importance of the $i$-th kind of bad idea is $2^{i-1}$.

Sometimes, Mr. Oshiro grabs a pile of bad thoughts to recall. Oshiro watches these thoughts one by one and gains the bad ideas in them. In particular, when Mr. Oshiro sees the same kind of bad idea twice, he will think this idea is nothing, and in the next moment he will forget that he has ever seen this idea.

The importance of one recall is the sum of the importance of the bad ideas that Oshiro still remembers after he finishes watching these thoughts.

Naturally, in the Celestial Resort, Mr. Oshiro complains a lot to Madeline.

Many years later, when Madeline recalls her climbing trip, she no longer remembers how important each thought was to Oshiro. She only remembers the importance of some of Mr. Oshiro’s recalls, as well as the number of bad thoughts in the Celestial Resort and the number of possible bad ideas in each thought.

Can you help her find how many legal thought sequences satisfy every recall of Mr. Oshiro?

In particular, a thought can also be a complete mess, meaning it contains nothing.

Input Format

The first line contains three integers $n,q,k$, representing the number of bad thoughts, the number of pieces of information Madeline tells you ($q$), and the number of possible bad ideas in each thought.

The next $q$ lines each contain one piece of information, starting with the type $op$.

If $op = 0$, then three integers $l,r,val$ follow, meaning Madeline remembers that in some recall Mr. Oshiro grabbed the thoughts with indices in the interval $[l,r]$ to recall, and after the recall the importance was $val$.

If $op = 1$, then one integer $cnt$ follows, meaning Madeline corrected the $cnt$-th statement with $op = 0$. The $cnt$-th statement is something she remembered wrongly. It is guaranteed that this $cnt$-th statement exists and has not been corrected before. (You may assume that a corrected statement no longer exists.)

If $op = 2$, you need to output one integer, representing how many legal thought sequences satisfy all current recalls of Mr. Oshiro, modulo $998244353$.

Output Format

For each $op = 2$, output the number of valid sequences modulo $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

Hint

For $10\%$ of the testdata, $n,k \leq 5, q \leq 15$.

For $30\%$ of the testdata, $n,q \leq 1000$.

For an additional $10\%$ of the testdata, $k = 1$.

For an additional $15\%$ of the testdata, there is no operation of type $1$.

For $75\%$ of the testdata, $n \leq 30000, q \leq 80000, k \leq 20$.

For $100\%$ of the testdata, $n \leq 2 * 10^5, q \leq 10^6, k \leq 30, 0 \leq val < 2^k$.

Translated by ChatGPT 5