Một hôm nọ, Tiểu Chưng đang mải mê nằm dài ăn bánh su kem thì người bạn "độc ác" nhưng tốt bụng, lại bày ra một bài toán để ép Chưng code đến chết thì thôi.

"Muốn ăn thêm su kem hả? Vậy thì giải bài này trước đi đã!".

Chưng có một hộp su kem đặc biệt, được đánh số gồm ~n~ chiếc: ~a_0, a_1, a_2, . . ., a_{n-1}~.

Đây không phải hộp su kem bình thường, mỗi thao tác mà Chưng làm với hộp sẽ biến đổi vị trí, hương vị, và thậm chí cả độ ngọt của những chiếc bánh bên trong. Bạn còn kèm theo ~q~ thử thách với các loại như sau:

• ~0~ ~i~ ~x~: nếu ~i<n~ thì chèn giá trị ~x~ vào trước giá trị ~a_i~, ngược lại, nếu ~i = n~ thì chèn giá trị ~x~ vào sau giá trị ~a_{n-1}~.</p>

• ~1~ ~i~: xóa giá trị thứ ~a_i~ ra khỏi dãy số và dịch các số phía sau ~a_i~ lên phía trước một đơn vị.

• ~2~ ~l~ ~r~: đảo ngược các giá trị ~a_l, a_{l+1}, . . ., a_{r-1}~.

• ~3~ ~l~ ~r~ ~b~ ~c~: với mỗi ~i~ thuộc trong đoạn từ ~l \to r-1~, ta sẽ gán lại thành ~b.a_{i} + c~.

• ~4~ ~l~ ~r~: tính tổng các ~a_i~ trong đoạn từ ~l \to r-1~ và mod cho ~998244353~.

Chưng đã rất cố gắng hết sức để giải quyết vấn đề này nhưng đây là một chủ đề không thuộc sở trường của cậu ấy và phần nào lại rất sợ nên cậu ấy đang tha thiết cần sự giúp đỡ từ bạn. Bạn hãy giúp cậu ấy hoàn thành vấn đề này nhé.

Input:

• Dòng đầu tiên gồm một số nguyên ~n~ và ~q~, ~1 \le n, \, q \le 5 \cdot 10^5.~

• Dòng tiếp theo sẽ chứa n số nguyên ~a_i~ với ~0 \le a_i \le 998244353.~

• ~q~ dòng tiếp theo sẽ theo format như sau:

• ~0~ ~i~ ~x~ với ~0 \le i \le~ (độ dài dãy số tại thời điểm đó), ~0 \le x \le 998244353.~

• ~1~ ~i~ với ~0 \le i \le~ (độ dài dãy số tại thời điểm đó).

• ~2~ ~l~ ~r~ với ~0 \le l < r \le~ (độ dài dãy số tại thời điểm đó).

• ~3~ ~l~ ~r~ ~b~ ~c~ với ~0 \le l < r \le~ (độ dài dãy số tại thời điểm đó), ~0 \le b, c \le 998244353.~

• ~4~ ~l~ ~r~ với ~0 \le l < r \le~ (độ dài dãy số tại thời điểm đó).

Output:

Nếu là câu hỏi dạng ~4~ thì in ra tổng các ~a_i~ trong đoạn từ ~l \to r-1~ và lấy mod ~998244353~.

Sample Input 1

5 6
1 9 6 7 6
4 1 4
0 2 23
1 3
4 2 5
2 2 5
4 0 4

Sample Output 1

22
36
23