Gán đoạn và hợp thành hàm trên đoạn (Range Set Range Composite)

Nguồn: Library Checker

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ hàm affine $f_i(x)=a_ix+b_i$ modulo $998244353$. Query loại 0 gán tất cả hàm trong đoạn nửa mở $[l,r)$ thành cùng $f(x)=cx+d$. Query loại 1 tính $f_{r-1}(\cdots f_l(x)\cdots)$.

Input

Dòng đầu chứa $n,q$. Tiếp theo có $n$ dòng, dòng thứ $i$ chứa $a_i,b_i$ của hàm $f_i(x)=a_ix+b_i$. Mỗi trong $q$ dòng sau là:

• 0 l r c d: gán mọi hàm có chỉ số $l\le i<r$ thành $f_i(x)=cx+d$.
• 1 l r x: tính $f_{r-1}(f_{r-2}(\cdots f_l(x)\cdots))$.

Chỉ số là 0-based và đoạn là nửa mở $[l,r)$.

Output

Mỗi truy vấn loại 1 in giá trị hợp hàm modulo $998244353$.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,q\le5\cdot10^5$

• $0\le a_i,b_i,c,d,x<998244353$

• $0\le l<r\le n$

Ví dụ

Input

3 4
1 1
2 0
1 3
1 0 3 1
0 1 3 1 0
1 0 3 5
1 1 3 7

Output

7
6
7

Giải thích

Hợp ba hàm ban đầu tại $x=1$ cho 7. Sau khi gán hai hàm cuối thành đồng nhất, hai truy vấn tiếp theo cho 6 và 7.