Problem Background

"We will never forget the time we spent here."

"There is no other place that makes me feel at peace. Thank you."

"It's a pity, Mr. Oshiro, the mountain villa is closing down."

"I will catch up with them until everything here is in order..."

"Where should I go after leaving this mountain villa?"

Problem Description

The Sky Resort is a villa located halfway up Celeste Mountain, which has been abandoned for a long time.

When Madeline arrived at this villa, only a ghost, Mr. Oshiro, was left to manage the villa alone.

Due to the magical power of the villa, it contains many of Mr. Oshiro's negative thoughts.

A thought may contain $k$ types of negative ideas, such as the villa closing down, being ignored, and not being understood, etc. Each idea has a different importance level for Mr. Oshiro. Specifically, the importance of the $i$-th negative idea is $2^{i-1}$.

Sometimes, Mr. Oshiro will pick up a pile of bad thoughts to reminisce. He will view these thoughts one by one and gain the negative ideas within them. Notably, when Mr. Oshiro sees the same negative idea twice, he will consider it insignificant and immediately forget that he has seen this idea before.

The importance of a reminiscence for Mr. Oshiro is the sum of the importance levels of the ideas he remembers after viewing these thoughts.

Naturally, at the Sky Resort, Mr. Oshiro poured out his grievances to Madeline.

Years later, when Madeline recalled her mountain climbing journey, she no longer remembered the importance of each thought for Mr. Oshiro. She only remembered the importance levels of some of Mr. Oshiro's reminiscences and the number of negative ideas in the Sky Resort and the number of possible negative ideas in each thought.

Can you help her find out how many valid sequences of thoughts satisfy each of Mr. Oshiro's reminiscences?

Notably, a thought may also be a mess, i.e., it contains nothing.

Input Format

The first line contains three integers $n, q, k$, representing the number of negative ideas, the number of pieces of information Madeline told you, and the number of possible negative ideas in each thought.

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

If $op = 0$, then three integers $l, r, val$ follow, indicating that Madeline remembered a reminiscence where Mr. Oshiro picked up thoughts numbered in the interval $[l, r]$, and the importance level after the reminiscence was $val$.

If $op = 1$, then an integer $cnt$ follows, indicating that Madeline corrected the $cnt$-th $op = 0$ statement, which was a mistake she remembered. It is guaranteed that the $cnt$-th statement exists and has not been corrected before. (You can consider that the corrected statement no longer exists)

If $op = 2$, you need to output an integer, representing the number of valid thought sequences that satisfy each of Mr. Oshiro's reminiscences, modulo $998244353$.

Output Format

For each $op = 2$, output the number of valid thought sequences, modulo $998244353$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

16

Sample Input #2

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

Sample Output #2

1

Sample Input #3

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

Sample Output #3

155712307
76042715
719747106
76042715
76042715
74890016
76042715
719747106

Notes

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

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

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

For an additional $15\%$ of the data, there are no operations of type 1

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

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

见题面 Input 部分

见题面 Output 部分