你在当地游乐园注意到一个旋转咖啡杯游乐设施。观察片刻后，你发现了关于该设施的一些有趣之处。

该设施由 $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