Chưng là một người rất lười implement. Vì vậy, để giúp cậu ấy tiến bộ hơn, Quýt đã đưa ra bài toán để cậu ấy code tới chết thì thôi :))).

Quýt cho Chưng một dãy số gồm ~n~ nguyên ~a_0, a_1, a_2, . . ., a_{n-1}~ và một bộ ~q~ câu hỏi. Với mỗi câu hỏi sẽ có các dạng 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ợ Quýt giận 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