あなたは地元の遊園地で、回転するティーカップの乗り物を見つけました。少し観察していると、この乗り物についていくつかの興味深いことに気づきました。

この乗り物は $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$ を持つ人が、2つのティーカップの中心を結ぶ直線上にいる場合、その人の幸福度は $w$ となります。それ以外の場合、その人の幸福度は 0 です。合計幸福度は大きくなる可能性があるため、998 244 353 で割った余りを出力してください。

参加者の合計幸福度を追跡するプログラムを作成してください。

入力

最初の行には、2つの整数 $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