Trong một ngày đêm u ám, p2o2HuaGiaBao bị bắt cóc vào khu tự trị nơi tồn tại khu lừa đảo lớn nhất Cam-pu-chia. Sếp bắt cóc anh ta vì thấy anh ấy có tiềm năng để lừa người nên mới bắt p2o2HuaGiaBao.
Bổng dưng, sếp maiphucthinhpika34 hỏi anh ấy đúng một câu:

Tôi cho bạn một trong 2 lựa chọn: Một là giải bài toán hóc búa này để được thả tự do vì chính sếp cũng chả biết giải (._.). Hai là sẽ giữ lại để làm việc cho hắn và sẽ cho ăn quả chích điện nếu không lừa được \(100\) người mỗi ngày.

Vì không muốn lừa chính người dân của mình nên p2o2HuaGiaBao chọn phương án số \(1\), vì bài toán dưới đây quá khó, mà không AC thì đẩy sang phương án số \(2\) nên đành nhanh trí nhờ sự trợ giúp bên ngoài. Các bạn hãy mau nhanh chóng giúp cậu ấy thoát khỏi ổ lừa đảo nhất quả đất Cam-pu-chia nhé!

Một dãy số (\(x_1,x_2,\ldots,x_m\)) được gọi là 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 \(\text{XOR bit}\).

Mọi dãy có độ dài \(1\) hoặc \(2\) đều là dãy Teto. Cho \(n\) đoạn \([l,r]\) (có thể trùng nhau).
Gọi \(P\) là tập hợp tất cả các số nguyên xuất hiện trong ít nhất một đoạn. Tạo dãy \(A\) gồm các phần tử của \(P\), sắp xếp tăng dần.

Cần đếm số lượng dãy con không rỗng của \(A\) là dãy Teto.
Kết quả lấy \(\text{mod}\) \(998244353\)
Sau đó có \(q\) thao tác động:

• 1 l r: thêm đoạn \([l,r]\).
• 2 l r: xóa một lần xuất hiện của đoạn \([l,r]\).

Sau trạng thái ban đầu và sau mỗi truy vấn, phải in ra số dãy con Teto hiện tại.

Input

• Dòng đầu chứa hai số nguyên \(n, q\) (\(1\le n\le 10^5\), \(0\le q\le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i\) mô tả một đoạn ban đầu \([l_i,r_i]\) (\(1\le l_i < r_i\le 10^9\)).
• \(q\) dòng tiếp theo mô tả các thao tác. (Lưu ý: Các dữ liệu trong mỗi truy vấn đều thỏa mãn tính hợp lí và yêu cầu đề bài)

Output

• In ra \(q+1\) dòng.
• Dòng đầu tiên là đáp án của trạng thái ban đầu.
• \(q\) tiếp theo là đáp án sau khi thực hiện xong thao tác tương ứng.

Example

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

7
7
7
12
3

3 3
10 12
15 15
100 101
1 12 13
1 14 14
2 10 12

39
60
84
39