Truy vấn hai dãy (Two Sequence Queries)

Nguồn: AtCoder

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

Đề bài

Có hai dãy $A,B$. Loại 1 cộng $x$ vào một đoạn của $A$, loại 2 cộng $x$ vào một đoạn của $B$, loại 3 hỏi $\sum A_iB_i$ trên đoạn modulo $998244353$.

Input

Dòng đầu chứa $N,Q$. Dòng thứ hai chứa dãy $A$, dòng thứ ba chứa dãy $B$. Mỗi trong $Q$ dòng sau là một trong ba dạng 1 l r x, 2 l r x, 3 l r như mô tả đề bài.

Output

Mỗi truy vấn loại 3 in đáp án 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\le2\cdot10^5$

• $0\le A_i,B_i\le10^9$

• $1\le x\le10^9$

Ví dụ

Input

3 5
1 2 3
4 5 6
3 1 3
1 1 2 10
3 1 2
2 2 3 2
3 1 3

Output

32
104
152

Giải thích

Ban đầu $\sum A_iB_i=32$. Sau khi cộng 10 vào $A_1,A_2$, truy vấn [1,2] bằng 104. Sau khi cộng 2 vào $B_2,B_3$, tổng toàn đoạn bằng 152.