Một dãy số nguyên không rỗng ~x_1, x_2, \dots, x_m~ được gọi là dãy Teto nếu với mọi ~1 \le i \le m - 2~,

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

trong đó ~\oplus~ là phép XOR bit^∗. Theo định nghĩa này, mọi dãy có độ dài ~1~ hoặc ~2~ đều là dãy Teto.

Bạn được cho một danh sách ~S~ gồm ~n~ đoạn số nguyên (các đoạn trong ~S~ có thể trùng nhau). Gọi ~P~ là tập tất cả các số nguyên nằm trong ít nhất một đoạn thuộc ~S~, và ~A~ là dãy gồm tất cả các phần tử của ~P~, được sắp xếp theo thứ tự tăng dần.

Bạn cần đếm số lượng dãy con^† không rỗng của ~A~ là dãy Teto. Hai dãy con được xem là khác nhau nếu tồn tại một phần tử thuộc dãy này nhưng không thuộc dãy kia. Vì kết quả có thể rất lớn, hãy in phần dư của nó khi chia cho ~998\,244\,353~.

Hơn nữa, bạn cần xử lý ~q~ cập nhật. Các cập nhật không độc lập — mỗi cập nhật thay đổi danh sách ~S~ và ảnh hưởng đến các cập nhật sau. Mỗi cập nhật thuộc một trong hai loại sau:

• 1 l r: thêm đoạn ~[l, r]~ vào ~S~.

• 2 l r: xóa đoạn ~[l, r]~ khỏi ~S~.

Với trạng thái ban đầu của ~S~ và sau mỗi cập nhật, hãy in số lượng dãy con không rỗng của ~A~ là dãy Teto, chia lấy dư cho ~998244353~.

∗ Phép XOR bit, ký hiệu ~\oplus~, là phép toán nhị phân trên biểu diễn bit của hai số nguyên. Một bit của kết quả bằng ~1~ khi hai bit tương ứng khác nhau, và bằng ~0~ khi hai bit tương ứng giống nhau.

† Một dãy con của ~A~ là một dãy thu được bằng cách xóa đi một số phần tử, có thể không xóa phần tử nào, khỏi ~A~ mà vẫn giữ nguyên thứ tự tương đối của các phần tử còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 100\,000~, ~0 \le q \le 100\,000~).

• Mỗi dòng trong ~n~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~, mô tả một đoạn ban đầu ~[l_i, r_i]~ (~1 \le l_i \le r_i \le 10^{9}~).

• Mỗi dòng trong ~q~ dòng tiếp theo chứa ba số nguyên ~t_i~, ~u_i~, và ~v_i~ (~t_i \in \{1, 2\}~, ~1 \le u_i \le v_i \le 10^{9}~), mô tả một cập nhật theo định dạng ở trên. Dữ liệu đảm bảo rằng với mọi cập nhật loại 2, ~S~ đang chứa ít nhất một đoạn ~[u_i, v_i]~.

Output

In ra ~q + 1~ dòng:

• Dòng đầu tiên chứa đáp án ở trạng thái ban đầu.

• Với mỗi ~1 \le i \le q~, dòng thứ ~(i + 1)~ chứa đáp án sau khi thực hiện ~i~ cập nhật đầu tiên.

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

Ban đầu ~S = \{[6, 7], [10, 10]\}~, nên ~P = \{6, 7, 10\}~ và ~A = [6, 7, 10]~. Mọi dãy con không rỗng của ~A~ đều là dãy Teto, nên đáp án là ~2^3 - 1 = 7~.

Sau cập nhật 1 6 7, ta thêm đoạn ~[6, 7]~ vào ~S~. Khi đó ~S = \{[6, 7], [6, 7], [10, 10]\}~, nhưng ~P~ vẫn là ~\{6, 7, 10\}~, nên ~A~ không đổi. Vì vậy, đáp án vẫn là ~7~.

Sau cập nhật 2 6 7, ta xóa một đoạn ~[6, 7]~ khỏi ~S~. Vì trong ~S~ vẫn còn đoạn ~[6, 7]~, nên ~P~ và ~A~ vẫn không đổi. Vì vậy, đáp án vẫn là ~7~.

Sau cập nhật 1 9 9, ta thêm đoạn ~[9, 9]~ vào ~S~. Khi đó ~P = \{6, 7, 9, 10\}~ và ~A = [6, 7, 9, 10]~.

Có tất cả ~15~ dãy con không rỗng của ~A~. Trong đó, đúng ~3~ dãy không phải là dãy Teto: ~[6, 9, 10]~ vì ~6 \oplus 9 = 15~ và ~9 \oplus 10 = 3~; ~[7, 9, 10]~ vì ~7 \oplus 9 = 14~ và ~9 \oplus 10 = 3~; và ~[6, 7, 9, 10]~ vì ~7 \oplus 9 = 14~ và ~9 \oplus 10 = 3~. Vậy đáp án là ~15 - 3 = 12~.

Sau cập nhật 2 6 7, đoạn ~[6, 7]~ còn lại bị xóa khỏi ~S~. Khi đó ~P = \{9, 10\}~ và ~A = [9, 10]~. Có đúng ~3~ dãy con Teto là ~[9]~, ~[10]~, và ~[9, 10]~.