H. Chia dãy nhị phân
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chung có dãy $$$a$$$ gồm $$$n$$$ số nhị phân, được đánh số bắt đầu từ 1 ($$$a_1,a_2,\cdots,a_n$$$). Ban đầu toàn bộ dãy $$$a$$$ bằng 0.

Hãy xử lý các truy vấn sau:

  • $$$1 \; i$$$ ($$$1 \le 1 \le n$$$): Flip giá trị phần tử $$$a_i$$$.
  • $$$2 \; l \; r$$$ $$$ $$$ ($$$1 \le l \le r \le n$$$): Đếm số cách chia đoạn $$$[l,r]$$$ thành các đoạn con liên tiếp sao cho mỗi phần tử $$$a_i$$$ ($$$i \in [l,r]$$$) thuộc đúng 1 đoạn và mỗi đoạn chứa ít nhất một số 1, chia lấy dư cho $$$998244353$$$.
Input

Dòng đầu tiên chứa số nguyên dương $$$t$$$ ($$$t \le 100$$$)— số testcase.

Mỗi testcase được mô tả như sau:

  • Dòng đầu tiên chứa số nguyên dương $$$n,q$$$ ($$$1 \le n,q \le 5 \cdot 10^5$$$) — Độ dài dãy nhị phân.
  • $$$q$$$ dòng tiếp theo chứa truy vấn được mô tả như trên.

Dữ liệu đầu vào đảm bảo tổng $$$n$$$ và tổng $$$q$$$ trong tất cả các testcase nhỏ hơn hoặc bằng $$$5 \cdot 10^5$$$;

Output

Với mỗi truy vấn 2, in ra đáp án tìm được.

Example
Input
1
5 6
1 1
1 3
1 4
2 1 4
1 1
2 1 5
Output
6
2
Note

Một cách chia là việc chia đoạn $$$[l,r]$$$ thành các đoạn $$$[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$$$ ($$$1 \le k$$$) sao cho $$$l_1=l,r_k=r$$$ và $$$l_i=r_{i-1}+1 \; \forall i \in [2,k]$$$.

Giải thích ví dụ:

  • Sau truy vấn 1: dãy $$$a$$$ trở thành $$$10000$$$.
  • Sau truy vấn 2: dãy $$$a$$$ trở thành $$$10100$$$.
  • Sau truy vấn 3: dãy $$$a$$$ trở thành $$$10110$$$.
  • Ở truy vấn 4, có 6 cách chia đoạn $$$[1,4]$$$ như sau:
    • $$$[1,3],[4,4]$$$
    • $$$[1,2],[3,3],[4,4]$$$
    • $$$[1,1],[2,3],[4,4]$$$
    • $$$[1,4]$$$
    • $$$[1,2],[3,4]$$$
    • $$$[1,1],[2,4]$$$
  • Sau truy vấn 5: dãy $$$a$$$ trở thành $$$00110$$$.
  • Ở truy vấn 6, có 2 cách chia đoạn $$$[1,5]$$$ như sau:
    • $$$[1,3],[2,5]$$$
    • $$$[1,5]$$$