A non-empty sequence of integers ~x_1, x_2, \dots, x_m~ is called a Teto sequence if for every ~1 \le i \le m - 2~,

$$x_i \oplus x_{i+1} < x_{i+1} \oplus x_{i+2},$$

where ~\oplus~ denotes the bitwise XOR^∗. By this definition, every sequence of length ~1~ or ~2~ is a Teto sequence.

You are given a list ~S~ of ~n~ intervals of integers (the intervals in ~S~ may repeat). Let ~P~ be the set of all integers that belong to at least one interval in ~S~, and let ~A~ be the sequence consisting of all elements of ~P~, sorted in increasing order.

You need to count the number of non-empty subsequences^† of ~A~ that are Teto sequences. Two subsequences are considered different if there exists one element in one sequence but not in the other. Since the result may be very large, output it modulo ~998\,244\,353~.

In addition, you need to process ~q~ updates. The updates are not independent — each update changes the list ~S~ and affects the following updates. Each update is of one of the following two types:

• 1 l r: add the interval ~[l, r]~ to ~S~.

• 2 l r: remove the interval ~[l, r]~ from ~S~.

For the initial state of ~S~ and after each update, print the number of non-empty subsequences of ~A~ that are Teto sequences, modulo ~998244353~.

∗ Bitwise XOR, denoted by ~\oplus~, is a binary operation on the bit representations of two integers. A bit of the result is ~1~ when the corresponding bits are different, and ~0~ when they are the same.

† A subsequence of ~A~ is a sequence obtained by deleting some elements, possibly none, from ~A~ while keeping the relative order of the remaining elements unchanged.

Input

• The first line contains two integers ~n~ and ~q~ (~1 \le n \le 100\,000~, ~0 \le q \le 100\,000~).

• Each of the next ~n~ lines contains two integers ~l_i~ and ~r_i~, describing an initial segment ~[l_i, r_i]~ (~1 \le l_i \le r_i \le 10^{9}~).

• Each of the next ~q~ lines contains three integers ~t_i~, ~u_i~, and ~v_i~ (~t_i \in \{1, 2\}~, ~1 \le u_i \le v_i \le 10^{9}~), describing an update in the format above. It is guaranteed that for every type 2 update, ~S~ contains at least one segment ~[u_i, v_i]~.

Output

Print ~q + 1~ lines:

• The first line contains the answer for the initial state.

• For each ~1 \le i \le q~, the ~(i + 1)~-th line contains the answer after performing the first ~i~ updates.

Scoring

Sample Input 1

2 4
6 7
10 10
1 6 7
2 6 7
1 9 9
2 6 7

Sample Output 1

7
7
7
12
3

Notes

Initially, ~S = \{[6, 7], [10, 10]\}~, so ~P = \{6, 7, 10\}~ and ~A = [6, 7, 10]~. Every non-empty subsequence of ~A~ is a Teto sequence, so the answer is ~2^3 - 1 = 7~.

After the update 1 6 7, we add the segment ~[6, 7]~ to ~S~. Then ~S = \{[6, 7], [6, 7], [10, 10]\}~, but ~P~ is still ~\{6, 7, 10\}~, so ~A~ does not change. Therefore, the answer is still ~7~.

After the update 2 6 7, we remove one segment ~[6, 7]~ from ~S~. Since ~S~ still contains another segment ~[6, 7]~, ~P~ and ~A~ remain unchanged. Therefore, the answer is still ~7~.

After the update 1 9 9, we add the segment ~[9, 9]~ to ~S~. Then ~P = \{6, 7, 9, 10\}~ and ~A = [6, 7, 9, 10]~.

There are ~15~ non-empty subsequences of ~A~ in total. Among them, exactly ~3~ are not Teto sequences: ~[6, 9, 10]~ because ~6 \oplus 9 = 15~ and ~9 \oplus 10 = 3~; ~[7, 9, 10]~ because ~7 \oplus 9 = 14~ and ~9 \oplus 10 = 3~; and ~[6, 7, 9, 10]~ because ~7 \oplus 9 = 14~ and ~9 \oplus 10 = 3~. Thus, the answer is ~15 - 3 = 12~.

After the update 2 6 7, the remaining segment ~[6, 7]~ is removed from ~S~. Then ~P = \{9, 10\}~ and ~A = [9, 10]~. There are exactly ~3~ Teto subsequences: ~[9]~, ~[10]~, and ~[9, 10]~.