Vous êtes dans un parc d'attractions local et vous remarquez une attraction de tasses tournantes. Après l'avoir observée un moment, vous remarquez quelques faits intéressants à propos de l'attraction.

L'attraction se compose de $N$ tasses circulaires, toutes espacées équitablement autour de la circonférence d'un plateau tournant : pour $i = 0, 1, \dots, N - 1$, la $i$-ème tasse est centrée au point qui est initialement à $i \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre par rapport au Nord.

Le plateau tournant est assez grand pour accueillir toutes les tasses sans qu'elles ne se cognent les unes aux autres. Dans chaque tasse, il y a $N$ personnes, toutes espacées équitablement autour de la circonférence de la tasse : pour $j = 0, 1, \dots, N - 1$, la $j$-ème personne est située au point qui est initialement à $j \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre par rapport au Nord. Comme les tasses sont assez grandes, considérez les personnes comme des points. Dans chaque tasse, pour $j = 0, 1, \dots, N - 1$, la $j$-ème personne a une valeur de bonheur $v_j$.

Notez que les personnes situées à la même position initiale dans des tasses différentes ont la même valeur de bonheur.

Au cours de $Q$ millisecondes, l'un des deux événements suivants se produit chaque milliseconde :

• Le plateau tournant tourne de $k_i \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre. Les tasses compensent ce mouvement, de sorte que leurs orientations par rapport à l'extérieur du plateau tournant ne sont pas affectées.
• La tasse située actuellement à $q_i \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre par rapport au Nord tourne de $k_i \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre autour de son centre. Les autres tasses ne sont pas affectées.

Vous souhaitez calculer le bonheur total de toutes les personnes, initialement et après chaque événement. Le bonheur total est la somme du bonheur individuel des personnes. Si une personne avec une valeur de bonheur $w$ se trouve sur une ligne droite formée par les centres de deux tasses, son bonheur est égal à $w$. Sinon, son bonheur est nul. Comme le bonheur total peut être grand, veuillez afficher le résultat modulo 998 244 353.

Veuillez écrire un programme pour suivre le bonheur total des participants !

Entrée

La première ligne contient deux entiers $N$ et $Q$ ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$).

La ligne suivante contient $N$ entiers, les valeurs $v_0, v_1, \dots, v_{N-1}$ ($1 \le v_i \le 1\,000\,000$).

Les $Q$ lignes suivantes décrivent les événements. Chaque ligne est formatée soit comme « 1 $k_i$ » ($1 \le k_i \le N$), indiquant que le plateau tournant tourne de $k_i \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre, soit comme « 2 $q_i$ $k_i$ » ($0 \le q_i < N$, $1 \le k_i \le N$), indiquant que la tasse située actuellement à $q_i \cdot \frac{360}{N}$ degrés (depuis le sommet) tourne de $k_i \cdot \frac{360}{N}$ degrés dans le sens des aiguilles d'une montre autour de son centre.

Sortie

Affichez $Q + 1$ lignes, chacune contenant le bonheur total après 0, 1, 2, \dots, $Q$ événements.

N'oubliez pas d'afficher le bonheur modulo 998 244 353.

Exemples

Entrée 1

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

Sortie 1

189
168
210
252