Description

On a dark night, Kurousagi Kotori tossed and turned in bed. Unable to sleep, she remembered a tragic OI contest experience years ago. It was a basic Binary Indexed Tree problem.

Given an array $A$ of length $n$, initially all $0$, perform $m$ operations of two types:

• $1\ x$: set $A_x$ to $(A_x + 1) \bmod 2$.
• $2\ l\ r$: ask for $(\sum_{i=l}^r A_i) \bmod 2$.

Although Kotori was quite simple back then, she still noticed that this problem could be solved using a Binary Indexed Tree. When she was very young, she wrote the following algorithm:

Here $\mathrm{lowbit}(x)$ denotes the lowest nonzero binary bit of number $x$, e.g., $\text{lowbit}(5) = 1, \text{lowbit}(12) = 4$. For the first type of operation she calls $\mathrm{Add}(x)$, and for the second type the answer is $\mathrm{Query}(l, r)$.

If you are familiar with Binary Indexed Trees, it is not hard to see that Kotori wrote it incorrectly: the direction in which $x$ changes in $\text{Add}$ and $\text{Find}$ is reversed. Therefore, this program spectacularly got a score of $0$ in the final test.

Strangely, at that time, this program passed the large sample test provided by the problem setter—this is also why Kotori did not conduct stress testing.

Now, Kotori wants to compute the probability that this program answers each query correctly, so she can once again feel how “fei” she was. However, many years have passed, and even Kotori cannot fully remember the large sample. Fortunately, she recalls most of it; the only thing she forgot is the value of $x$ for each type 1 operation, so she assumes that $x$ is chosen uniformly at random from the range $[l_i, r_i]$ for that operation.

Specifically, Kotori gives an array $A$ of length $n$, initially $0$, and then performs $m$ operations:

• $1\ l\ r$: uniformly at random pick an $x$ in the interval $[l, r]$ and execute $\text{Add}(x)$.
• $2\ l\ r$: ask for the probability that executing $\text{Query}(l, r)$ yields the correct result.

Input Format

The first line contains two integers $n, m$.

Each of the next $m$ lines describes one operation in the format specified above.

Output Format

For each query, output one integer representing the answer. If the simplified fraction of the answer is $\frac x y$, you only need to output the value of $x \times y^{-1} \bmod 998244353$ (that is, output the answer modulo $998244353$).

5 5
1 3 3
2 3 5
2 4 5
1 1 3
2 2 5

1
0
665496236

Hint

• Sample Explanation:

  After performing $\mathrm{Add}(3)$, the array $A$ becomes $[0, 1, 1, 0, 0]$. Therefore, the program’s answers for the first two queries are both $1$. Hence, the first query is certainly correct, and the second query is certainly incorrect.

• Constraints:

  • Test point 1: $n \le 5$, $m \le 10$, no additional constraints.
  • Test point 2: $n \le 50$, $m \le 50$, no additional constraints.
  • Test point 3: $n \le 50$, $m \le 50$, no additional constraints.
  • Test point 4: $n \le 3 \times 10^3$, $m \le 3 \times 10^3$, no additional constraints.
  • Test point 5: $n \le 3 \times 10^3$, $m \le 3 \times 10^3$, no additional constraints.
  • Test point 6: $n = 10^5$, $m = 10^5$, all queries occur after updates.
  • Test point 7: $n = 10^5$, $m = 10^5$, all queries occur after updates.
  • Test point 8: $n = 10^5$, $m = 10^5$, no additional constraints.
  • Test point 9: $n = 10^5$, $m = 10^5$, no additional constraints.
  • Test point 10: $n = 10^5$, $m = 10^5$, no additional constraints.

  For $100\%$ of the testdata, it is guaranteed that $1 \le l \le r \le n$.

  Update: 2018/05/13 @larryzhong provided 5 stronger testdata sets.

Translated by ChatGPT 5