Keke is a girl who loves data structures. Among common data structures, her favorite is the segment tree.

The core of a segment tree is the lazy tag. Below is the pseudocode for a segment tree with lazy tags, where the tag array stores the lazy tags:

1: function Pushdown(Node)
2: if tag[Node]= 1 then
3: tag[Lson(Node)]← 1
4: tag[Rson(Node)]← 1
5: tag[Node]← 0
6: end if
7: end function
8:
9: function Modify(Node, l, r, ql, qr)
10: if [l, r] ∩ [ql, qr] = ∅ then
11: return
12: end if
13: if [l, r] ⊆ [ql, qr] then
14: tag[Node] ← 1
15: return
16: end if
17: m ← ⌊(l + r) / 2⌋
18: Pushdown(Node)
19: Modify(Lson(Node),l, m, ql, qr)
20: Modify(Rson(Node),m + 1, r, ql, qr)
21: end function

Here, the function Lson(Node) represents the left child of Node, and Rson(Node) represents the right child of Node.

Keke currently has a segment tree on $[1, n]$, numbered 1. All nodes in this segment tree have a tag of 0. Keke then performs $m$ operations of two types:

• 1 l r: Suppose Keke currently has $t$ segment trees. She will duplicate each segment tree twice (the tag array is also copied). The two copies of the original segment tree $i$ are numbered $2i - 1$ and $2i$. After the duplication, Keke has a total of $2t$ segment trees. Then, Keke performs Modify(root, 1, n, l, r) on all segment trees with odd numbers.
• 2: Keke defines the weight of a segment tree as the number of nodes in it that have a tag of 1. Keke wants to know the sum of the weights of all the segment trees she currently has.

Input

The first line contains two integers $n, m$, representing the initial interval length and the number of operations.

The next $m$ lines each describe an operation. It is guaranteed that $1 \le l \le r \le n$.

Output

For each query, output a single integer representing the answer. Since the answer can be very large, output it modulo 998244353.

Examples

Input 1

5 5
2
1 1 3
2
1 3 5
2

Output 1

0
1
6

Note

The segment tree on $[1, 5]$ is shown below:

At the first query, Keke has one segment tree, and none of its nodes have a tag, so the answer is 0.

At the second query, Keke has two segment trees. According to their numbering, their tag status is:

1. Node $[1, 3]$ has a tag, weight is 1.
2. No nodes have a tag, weight is 0.

Therefore, the answer is 1.

At the third query, Keke has four segment trees. According to their numbering, their tag status is:

1. Nodes $[1, 2], [3, 3], [4, 5]$ have tags, weight is 3.
2. Node $[1, 3]$ has a tag, weight is 1.
3. Nodes $[3, 3], [4, 5]$ have tags, weight is 2.
4. No nodes have a tag, weight is 0.

Therefore, the answer is 6.