你在當地的遊樂園，注意到了一個旋轉咖啡杯遊樂設施。觀察了一陣子後，你發現了關於這個設施的一些有趣現象。

該設施由 $N$ 個圓形咖啡杯組成，它們均勻分佈在轉盤的圓周上：對於 $i = 0, 1, \dots, N - 1$，第 $i$ 個咖啡杯的中心初始位置位於從北方順時針旋轉 $i \cdot \frac{360}{N}$ 度的點上。

轉盤足夠大，可以容納所有咖啡杯而不會互相碰撞。在每個咖啡杯中，有 $N$ 個人均勻分佈在咖啡杯的圓周上：對於 $j = 0, 1, \dots, N - 1$，第 $j$ 個人初始位置位於從北方順時針旋轉 $j \cdot \frac{360}{N}$ 度的點上。由於咖啡杯足夠大，我們將人視為點。在每個咖啡杯中，對於 $j = 0, 1, \dots, N - 1$，第 $j$ 個人的幸福值為 $v_j$。

請注意，不同咖啡杯中處於相同初始位置的人具有相同的幸福值。

在 $Q$ 毫秒的過程中，每一毫秒會發生以下兩種事件之一：

• 轉盤順時針旋轉 $k_i \cdot \frac{360}{N}$ 度。咖啡杯會進行補償，使得它們相對於轉盤外部的方位不受影響。
• 目前位於從北方順時針旋轉 $q_i \cdot \frac{360}{N}$ 度的咖啡杯，繞其中心順時針旋轉 $k_i \cdot \frac{360}{N}$ 度。其他咖啡杯不受影響。

你想要計算初始狀態以及每次事件發生後所有人的總幸福值。總幸福值是每個人幸福值的總和。如果一個幸福值為 $w$ 的人位於由兩個咖啡杯中心所形成的直線上，則他們的幸福值等於 $w$。否則，他們的幸福值為零。由於總幸福值可能很大，請輸出其對 $998\,244\,353$ 取模後的結果。

請編寫一個程式來追蹤參與者的總幸福值！

輸入格式

第一行包含兩個整數 $N$ 和 $Q$ ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$)。

下一行包含 $N$ 個整數，即數值 $v_0, v_1, \dots, v_{N-1}$ ($1 \le v_i \le 1\,000\,000$)。

接下來的 $Q$ 行描述事件。每行的格式為 “1 $k_i$” ($1 \le k_i \le N$)，表示轉盤順時針旋轉 $k_i \cdot \frac{360}{N}$ 度；或者 “2 $q_i$ $k_i$” ($0 \le q_i < N$, $1 \le k_i \le N$)，表示目前位於從頂部順時針旋轉 $q_i \cdot \frac{360}{N}$ 度的咖啡杯繞其中心順時針旋轉 $k_i \cdot \frac{360}{N}$ 度。

輸出格式

輸出 $Q + 1$ 行，每一行包含 0, 1, 2, \dots, $Q$ 次事件後的總幸福值。

記得將幸福值對 $998\,244\,353$ 取模。

範例

輸入 1

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

輸出 1

189
168
210
252