G. Game of Quantum Computing Chickens
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Colin is studying quantum game theory by watching his two quantum computing chickens, Chi and Ken, play a peculiar seed-picking game. Initially, there are several piles of seeds. The chickens take turns, with Chi moving first. The rules are:

  • If all piles are empty, the current chicken loses immediately.
  • Otherwise, the current chicken must take seeds from the largest pile. She must take at least one seed and may take all seeds from that pile.

Due to quantum entanglement, the initial pile sizes are uncertain. Colin models this using a multiset $$$S$$$, initially empty. He asks you to support two operations:

  • 1 x y: Add $$$y$$$ copies of number $$$x$$$ to the multiset $$$S$$$.
  • 2 l r: Generate a new multiset $$$S'$$$ as follows: for each $$$x \in S$$$, if $$$l \le x \le r$$$, include $$$x$$$ in $$$S'$$$ with probability $$$0.5$$$; otherwise, do nothing. You then need to compute the probability that Chi has a winning strategy when the piles are exactly the numbers in $$$S'$$$, modulo $$$998244353$$$. $$$S'$$$ will be discarded afterwards and doesn't change $$$S$$$.

Note that $$$S'$$$ may be empty, in which case the first chicken (Chi) loses.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 5 \times 10^5)$$$, the number of operations.

Each of the next $$$n$$$ lines contains three positive integers:

  • For type 1: 1 x y $$$(1 \le x, y \le 10^9)$$$.
  • For type 2: 2 l r $$$(1 \le l \le r \le 10^9)$$$.
Output

For each type 2 operation, output a line with a single integer: the probability that Chi has a winning strategy, modulo $$$998244353$$$.

Example
Input
6
1 1 1
2 1 1
1 1 1
2 1 1
1 2 2
2 1 2
Output
499122177
499122177
374341633
Note

For the example:

  • First query: $$$S = \{1\}$$$. $$$S'$$$ is empty with $$$0.5$$$ probability, or $$$\{1\}$$$ with $$$0.5$$$ probability. Chi wins only if $$$S' = \{1\}$$$.
  • Second query: $$$S = \{1,1\}$$$. Possible $$$S'$$$: empty (25%), $$$\{1\}$$$ (50%), $$$\{1,1\}$$$ (25%). Chi wins only if $$$S' = \{1\}$$$.
  • Third query: $$$S = \{1,1,2,2\}$$$. Probability calculation yields $$$374341633 \equiv \frac{5}{8} \pmod{998244353}$$$.