Strictly Increasing XOR Prefix and Suffix Sequence Queries

You are given two integers n and q. Initially, an integer m is set to 0. You need to process q operations. There are three types of operations:

• 0 x: Increase m by \(2^x\).
• 1 x: Decrease m by \(2^x\) if m \ge 2^x; otherwise, ignore the operation.
• 2: Query the number of strictly increasing sequences of positive integers of length n where each element is between 1 and m (inclusive), and both the prefix XOR sum array and the suffix XOR sum array are strictly increasing. The answer is given modulo \(998\,244\,353\).

The prefix XOR sum array for a sequence \(a_1, a_2, \dots, a_n\) is defined as follows:

\[ s_1 = a_1, \quad s_i = a_i \oplus s_{i-1} \; \text{for} \; i \ge 2, \]

The suffix XOR sum array is defined as:

\[ t_1 = a_n, \quad t_i = a_{n-i+1} \oplus t_{i-1} \; \text{for} \; i \ge 2, \]

Here, \(x \oplus y\) denotes the bitwise XOR of \(x\) and \(y\).

Note: A sequence \(a_1, a_2, \dots, a_n\) must be strictly increasing. It turns out that the only sequences satisfying the additional conditions on the XOR sums are as follows:

• If n = 1, any choice of \(a_1\) in \([1, m]\) is valid (since there is just one element).
• If n \ge 2, the only valid sequence is \(a_1 = 1, a_2 = 2, a_3 = 4, \dots, a_n = 2^{n-1}\). Thus the query answer is 1 if \(m \ge 2^{n-1}\) and 0 otherwise.

Process all the operations in the given order and output the answer for every query of type 2.

inputFormat

The first line contains two integers n and q separated by a space.

Each of the next q lines represents an operation in one of the following formats:

• 0 x or 1 x: where x is a non-negative integer.
• 2

outputFormat

For each operation of type 2, output on a new line the number of valid sequences modulo \(998\,244\,353\).

sample

1 3
2
0 1
2

0
2

</p>