Estás en un parque de atracciones local y observas una atracción de tazas giratorias. Tras observarla un poco, notas algunas cosas interesantes sobre la atracción.

La atracción consiste en $N$ tazas circulares, todas igualmente espaciadas alrededor de la circunferencia de una plataforma giratoria: para $i = 0, 1, \dots, N - 1$, la $i$-ésima taza está centrada en el punto que inicialmente está a $i \cdot \frac{360}{N}$ grados en sentido horario desde el Norte.

La plataforma es lo suficientemente grande como para acomodar todas las tazas sin que choquen entre sí. En cada taza, hay $N$ personas, todas igualmente espaciadas alrededor de la circunferencia de la taza: para $j = 0, 1, \dots, N - 1$, la $j$-ésima persona está ubicada en el punto que inicialmente está a $j \cdot \frac{360}{N}$ grados en sentido horario desde el Norte. Como las tazas son lo suficientemente grandes, considera a las personas como puntos. En cada taza, para $j = 0, 1, \dots, N - 1$, la $j$-ésima persona tiene un valor de felicidad $v_j$.

Nota que las personas en la misma posición inicial en diferentes tazas tienen el mismo valor de felicidad.

A lo largo de $Q$ milisegundos, ocurre uno de dos eventos cada milisegundo:

• La plataforma gira $k_i \cdot \frac{360}{N}$ grados en sentido horario. Las tazas compensan esto, de modo que sus orientaciones relativas al exterior de la plataforma no se ven afectadas.
• La taza que actualmente se encuentra a $q_i \cdot \frac{360}{N}$ grados en sentido horario desde el Norte gira $k_i \cdot \frac{360}{N}$ grados en sentido horario alrededor de su centro. Las otras tazas no se ven afectadas.

Deseas calcular la felicidad total de todas las personas, inicialmente y después de cada evento. La felicidad total es la suma de la felicidad individual de las personas. Si una persona con valor de felicidad $w$ se encuentra en una línea recta formada por los centros de dos tazas, su felicidad es igual a $w$. De lo contrario, su felicidad es cero. Como la felicidad total puede ser grande, por favor imprímela módulo $998\,244\,353$.

Por favor, escribe un programa para realizar el seguimiento de la felicidad total de los participantes.

Entrada

La primera línea contiene dos enteros $N$ y $Q$ ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$).

La siguiente línea contiene $N$ enteros, los valores $v_0, v_1, \dots, v_{N-1}$ ($1 \le v_i \le 1\,000\,000$).

Las siguientes $Q$ líneas describen los eventos. Cada línea tiene el formato “1 $k_i$” ($1 \le k_i \le N$), indicando que la plataforma gira $k_i \cdot \frac{360}{N}$ grados en sentido horario, o “2 $q_i$ $k_i$” ($0 \le q_i < N$, $1 \le k_i \le N$) indicando que la taza que actualmente se encuentra a $q_i \cdot \frac{360}{N}$ grados (desde la parte superior) gira $k_i \cdot \frac{360}{N}$ grados en sentido horario alrededor de su centro.

Salida

Imprime $Q + 1$ líneas, cada una conteniendo la felicidad total después de $0, 1, 2, \dots, Q$ eventos.

Recuerda imprimir la felicidad módulo $998\,244\,353$.

Ejemplos

Entrada 1

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

Salida 1

189
168
210
252