Biến đổi affine và tổng đoạn (Range Affine Range Sum)

Nguồn: AtCoder

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

Đề bài

Hỗ trợ áp dụng hàm affine $x\mapsto bx+c$ trên một đoạn nửa mở và truy vấn tổng modulo $998244353$.

Input

Dòng đầu chứa $N,Q$, dòng kế chứa $a_0,\ldots,a_{N-1}$. Mỗi truy vấn:

• 0 l r b c: với $l\le i<r$, gán $a_i\leftarrow b a_i+c$ modulo $998244353$.
• 1 l r: in $\sum_{i=l}^{r-1}a_i$ modulo $998244353$.

Output

In một dòng cho mỗi truy vấn loại 1.

Subtask

• 20 điểm: $N,Q\le50$.
• 30 điểm: $N,Q\le5000$.
• 50 điểm: $N,Q\le5\cdot10^5$, $0\le a_i,c<998244353$, $1\le b<998244353$.

Ví dụ

Input

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5

Output

15
404
41511
4317767

Giải thích

Truy vấn đầu cho 15. Mỗi cập nhật là một hàm affine áp dụng theo đúng thứ tự thời gian; tính modulo sau từng phép biến đổi. Các truy vấn tiếp theo lần lượt cho 404, 41511, 4317767.