H. Whalica's Mysterious Set
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Whalica has a set $$$S$$$, and $$$S$$$ is initially empty. In addition, a parameter $$$n$$$ is given. You need to perform the given $$$q$$$ operations in order. There are four types of operations, and the format and meaning of each operation are as follows:

Operation $$$1$$$: $$$\texttt{1 x}$$$ Given an integer $$$x$$$ $$$(1\le x\le n)$$$, insert $$$x$$$ into the set $$$S$$$. In particular, if $$$S$$$ already contains the element $$$x$$$, then ignore this operation.

Operation $$$2$$$: $$$\texttt{2 x}$$$ Given an integer $$$x$$$ $$$(1\le x\le n)$$$, delete $$$x$$$ from the set $$$S$$$. In particular, if $$$S$$$ does not contain the element $$$x$$$, then ignore this operation.

Operation $$$3$$$: $$$\texttt{3}$$$ Query the smallest positive integer that does not appear in the set $$$S$$$.

Operation $$$4$$$: $$$\texttt{4}$$$ Query the weight of the set $$$S$$$. Here, the definition of the weight of the set $$$S$$$ is as follows: let the number of integers in the range $$$[1, n]$$$ that do not appear in the set $$$S$$$ be $$$k$$$, and let these $$$k$$$ elements in increasing order be $$$a_1, a_2, a_3, \cdots, a_k$$$, then the weight of the set $$$S$$$ is: $$$$$$ \sum_{i = 1}^{k} a_i \cdot 2^i $$$$$$ For each operation $$$4$$$, since the result may be very large, please take the result modulo $$$998244353$$$.

Input

The first line contains two integers $$$n, q$$$ ($$$1\le n, q \le 10^5$$$) — the given parameter and the number of queries.

Next come $$$q$$$ queries, one per line. Please refer to the statement for the format and meaning.

Output

For each operation $$$3$$$, output an integer, indicating the smallest positive integer that does not appear in the set $$$S$$$.

For each operation $$$4$$$, output an integer, indicating the weight of the set $$$S$$$, with the result taken modulo $$$998244353$$$.

Example
Input
5 7
1 1
1 2
1 2
2 2
2 3
3
4
Output
2
128
Note

Explanation for the example:

Operation No.Operation TypeOperation ResultElements in the Set
1Operation $$$1$$$Insert element $$$1$$$$$$\{1\}$$$
2Operation $$$1$$$Insert element $$$2$$$$$$\{1,2\}$$$
3Operation $$$1$$$The set $$$S$$$ already contains element $$$2$$$, ignore this operation$$$\{1,2\}$$$
4Operation $$$2$$$Delete element $$$2$$$$$$\{1\}$$$
5Operation $$$2$$$The set $$$S$$$ does not contain element $$$3$$$, ignore this operation$$$\{1\}$$$
6Operation $$$3$$$Query the smallest positive integer that does not appear in the set $$$S$$$, the result is $$$2$$$$$$\{1\}$$$
7Operation $$$4$$$Query the weight of the set $$$S$$$, the result is $$$2\times 2^1 + 3\times 2^2 + 4\times 2^3 + 5\times 2^4 = 4 + 12 + 32 + 80 = 128$$$$$$\{1\}$$$