Binary Indexed Tree

On a dark night, Kelei lies in bed, tossing and turning. Unable to sleep, she recalls a miserable OI competition experience from several years ago. It was a basic problem about Binary Indexed Trees (BIT).

Given an array $A$ of length $n$, initially all zeros, perform $m$ operations of two types: $1\ x$: Update $A_x$ to $(A_x + 1) \pmod 2$. $2\ l\ r$: Query $(\sum_{i=l}^r A_i) \pmod 2$.

Although Kelei was very simple at that time, she still discovered that this problem could be solved using a Binary Indexed Tree. Being very young then, she wrote the following algorithm:

function Add(x)
    while x > 0 do
        Ax ← (Ax + 1) mod 2
        x ← x − lowbit(x)
    end while
end function

function Find(x)
    if x == 0 then
        return 0
    end if
    ans ← 0
    while x ≤ n do
        ans ← (ans + Ax) mod 2
        x ← x + lowbit(x)
    end while
    return ans
end function

function Query(l, r)
    ansl ← Find(l − 1)
    ansr ← Find(r)
    return (ansr − ansl + 2) mod 2
end function

Here, $\text{lowbit}(x)$ denotes the lowest non-zero bit of the number $x$ in binary representation; for example, $\text{lowbit}(5) = 1$, $\text{lowbit}(12) = 4$. When performing the first type of operation, Add(x) is called, and for the second type, the answer is Query(l, r).

If you are familiar with Binary Indexed Trees, it is not hard to see that Kelei implemented the BIT incorrectly: the direction of change for $x$ in Add and Find is reversed. Consequently, this program scored a spectacular 0 in the final tests.

Strangely, however, the program passed the large sample cases provided by the problem setter at the time—which is why Kelei did not perform any stress testing.

Now, Kelei wants to calculate the probability that this program answers each query correctly, so she can once again feel how unlucky she is. However, many years have passed, and even Kelei cannot fully recall the large sample cases from back then. Fortunately, she remembers most of the content; the only thing forgotten is the value of $x$ for each first-type operation. Therefore, she assumes that the $x$ for this operation is chosen uniformly at random from the range $[l_i, r_i]$.

Specifically, Kelei provides an array $A$ of length $n$, initially all zeros, and performs $m$ operations: $1\ l\ r$: Choose an $x$ uniformly at random from the interval $[l, r]$ and execute Add(x). $2\ l\ r$: Query the probability that executing Query(l, r) yields the correct result.

Input

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

The next $m$ lines each describe an operation, in the format specified in the problem.

Output

For each query, output an integer representing the answer. If the answer, when expressed as an irreducible fraction $\frac{x}{y}$, is required, you only need to output the value of $x \times y^{-1} \pmod{998244353}$. (That is, output the answer modulo $998244353$).

Examples

Input 1

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

Output 1

1
0
665496236

Note 1

After performing Add(3), the array $A$ becomes $[0, 1, 1, 0, 0]$. Therefore, for the first two queries, Kelei's program answers $1$, so the first query is definitely correct, and the second query is definitely incorrect.

Constraints

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