Bạn đang ở một công viên giải trí địa phương và chú ý đến trò chơi tách trà xoay. Sau khi quan sát một lúc, bạn nhận thấy một vài điều thú vị về trò chơi này.

Trò chơi bao gồm $N$ tách trà, được đặt cách đều nhau xung quanh chu vi của một bàn xoay: với $i = 0, 1, \dots, N - 1$, tách trà thứ $i$ có tâm tại điểm ban đầu cách hướng Bắc $i \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ.

Bàn xoay đủ lớn để chứa tất cả các tách trà mà không va chạm vào nhau. Trong mỗi tách trà, có $N$ người, được đặt cách đều nhau xung quanh chu vi của tách trà: với $j = 0, 1, \dots, N - 1$, người thứ $j$ nằm tại điểm ban đầu cách hướng Bắc $j \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ. Vì các tách trà đủ lớn, hãy coi mỗi người là một điểm. Trong mỗi tách trà, với $j = 0, 1, \dots, N - 1$, người thứ $j$ có giá trị hạnh phúc là $v_j$.

Lưu ý rằng những người ở cùng vị trí ban đầu trong các tách trà khác nhau có cùng giá trị hạnh phúc.

Trong suốt $Q$ mili giây, một trong hai sự kiện sau xảy ra mỗi mili giây:

• Bàn xoay quay $k_i \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ. Các tách trà tự điều chỉnh để hướng của chúng so với bên ngoài bàn xoay không bị ảnh hưởng.
• Tách trà hiện đang ở vị trí $q_i \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ so với hướng Bắc sẽ quay $k_i \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ quanh tâm của nó. Các tách trà khác không bị ảnh hưởng.

Bạn muốn tính tổng hạnh phúc của tất cả mọi người, ban đầu và sau mỗi sự kiện. Tổng hạnh phúc là tổng giá trị hạnh phúc của từng cá nhân. Nếu một người có giá trị hạnh phúc $w$ nằm trên đường thẳng tạo bởi tâm của hai tách trà, hạnh phúc của họ bằng $w$. Ngược lại, hạnh phúc của họ bằng 0. Vì tổng hạnh phúc có thể rất lớn, hãy in ra kết quả theo modulo 998 244 353.

Hãy viết chương trình để theo dõi tổng hạnh phúc của những người tham gia!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$).

Dòng tiếp theo chứa $N$ số nguyên, các giá trị $v_0, v_1, \dots, v_{N-1}$ ($1 \le v_i \le 1\,000\,000$).

$Q$ dòng tiếp theo mô tả các sự kiện. Mỗi dòng được định dạng là "1 $k_i$" ($1 \le k_i \le N$), cho biết bàn xoay quay $k_i \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ, hoặc "2 $q_i$ $k_i$" ($0 \le q_i < N$, $1 \le k_i \le N$) cho biết tách trà hiện đang ở vị trí $q_i \cdot \frac{360}{N}$ độ (tính từ phía trên) quay $k_i \cdot \frac{360}{N}$ độ theo chiều kim đồng hồ quanh tâm của nó.

Dữ liệu ra

In ra $Q + 1$ dòng, mỗi dòng chứa tổng hạnh phúc sau 0, 1, 2, \dots, $Q$ sự kiện.

Hãy nhớ in ra giá trị hạnh phúc theo modulo 998 244 353.

Ví dụ

Dữ liệu vào 1

6 3
1 2 4 8 16 32
2 1 4
1 5
2 4 2

Dữ liệu ra 1

189
168
210
252