D. Alice Based
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob study at ESCOM, where a popular game called SIM is often played.

The game consists of $$$k$$$ piles of stones, where each pile contains a non-negative number of stones. The two players take turns (Alice goes first), and on each turn, a player must remove a square number of stones from a single pile. The player unable to make a move loses the game.

This game seems boring to them because the winner can be determined in advance if the exact number of stones is known. Since all members of the AlgoRitmo Club (including Alice and Bob) always play optimally, they decided to make the game more interesting.

They have a list $$$P$$$ of positive integers, initially empty. They can perform multiple actions on this list. Alice can add piles of stones. Bob, in turn, can remove any pile from $$$P$$$.

Each time they want to play SIM, they ask Marckess to randomly select stones from the current list $$$P$$$ to include them in the game. Each pile in $$$P$$$ is included in the final list $$$F$$$ with a $$$50\%$$$ chance, independently of the others. However, there is a chance that none of the piles in $$$P$$$ will be selected. To ensure the game always has at least one pile, Alice is allowed to add exactly one specific pile directly to $$$F$$$. This pile does not go through the random selection process and is not part of $$$P$$$.

They want to know the probability that Alice (the first player) will win for each game they play.

Input

The first line contains an integer $$$Q$$$ $$$(2 \leq Q \leq 2 \cdot 10^5)$$$ – the number of actions. The next $$$Q$$$ lines will each contain the description of the actions. The action of Alice and Bob are represented as follows:

  • $$$\mathbf{1\ x}$$$: Alice adds a pile of stones with size $$$x$$$ to the list $$$P$$$ (it is guaranteed that there will be no duplicates).
  • $$$\mathbf{2\ x}$$$: Bob removes a pile of stones with size $$$x$$$ from the list $$$P$$$ (it is guaranteed that this pile is currently in the list).
  • $$$\mathbf{3\ x}$$$: Alice adds a pile of stones with size $$$x$$$ directly to the final list $$$F$$$, and Marckess performs the random process to determine which piles from $$$P$$$ are added to $$$F$$$. Each pile in $$$P$$$ is included in $$$F$$$ independently with a probability of $$$\frac{1}{2}$$$.

The value of $$$x$$$ will be in the range $$$1 \leq x \leq 3 \cdot 10^5$$$ for all actions.

Output

For each query of type 3, print the probability that Alice wins the resulting game after Marckess completes the random selection.

The probability should be printed as the fraction $$$\frac{a}{b}$$$ represented modulo $$$998244353$$$, which means you need to calculate $$$(a \cdot b^{-1}) \mod 998244353$$$ where $$$b^{-1}$$$ is the modular multiplicative inverse of $$$b$$$ modulo $$$998244353$$$

Example
Input
5
1 2
1 3
3 6
2 2
3 9
Output
499122177
1
Note

For the first type-3 query:

At this point, the list $$$P$$$ contains the piles $$$\{2, 3\}$$$. After Marckess performs the random process, the following scenarios are possible:

  1. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains piles $$$\{2, 3, 6\}$$$. It can be proven that Bob always wins if both players play optimally.
  2. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains piles $$$\{2, 6\}$$$. Alice wins.
  3. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains piles $$$\{3, 6\}$$$. Bob wins.
  4. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains only the pile $$$\{6\}$$$. Alice always wins.

Thus, Alice wins with a probability of $$$\frac{1}{2}$$$.

For the second type-3 query:

At this point, the list $$$P$$$ contains the piles $$$\{3\}$$$. The following scenarios are possible:

  1. With probability $$$\frac{1}{2}$$$, the final list $$$F$$$ contains piles $$$\{3, 9\}$$$. Alice wins.
  2. With probability $$$\frac{1}{2}$$$, the final list $$$F$$$ contains only the pile $$$\{9\}$$$. Alice always wins.

Thus, Alice wins with a probability of $$$1$$$.