Jesteś w lokalnym wesołym miasteczku i obserwujesz karuzelę z filiżankami. Po chwili obserwacji zauważasz kilka interesujących rzeczy na temat tej atrakcji.

Atrakcja składa się z $N$ okrągłych filiżanek, rozmieszczonych w równych odstępach wzdłuż obwodu platformy: dla $i = 0, 1, \dots, N - 1$, $i$-ta filiżanka jest wyśrodkowana w punkcie, który początkowo znajduje się $i \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara od północy.

Platforma jest wystarczająco duża, aby pomieścić wszystkie filiżanki bez ich zderzania się. W każdej filiżance znajduje się $N$ osób, rozmieszczonych w równych odstępach wzdłuż obwodu filiżanki: dla $j = 0, 1, \dots, N - 1$, $j$-ta osoba znajduje się w punkcie, który początkowo znajduje się $j \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara od północy. Ponieważ filiżanki są wystarczająco duże, traktujemy ludzi jako punkty. W każdej filiżance, dla $j = 0, 1, \dots, N - 1$, $j$-ta osoba ma wartość szczęścia $v_j$.

Zauważ, że osoby znajdujące się w tej samej początkowej pozycji w różnych filiżankach mają taką samą wartość szczęścia.

W ciągu $Q$ milisekund, w każdej milisekundzie zachodzi jedno z dwóch zdarzeń:

• Platforma obraca się o $k_i \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara. Filiżanki kompensują ten ruch, więc ich orientacja względem otoczenia platformy pozostaje niezmieniona.
• Filiżanka znajdująca się aktualnie w pozycji $q_i \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara od północy obraca się o $k_i \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara wokół swojego środka. Pozostałe filiżanki pozostają bez zmian.

Chcesz obliczyć całkowite szczęście wszystkich osób, początkowo oraz po każdym zdarzeniu. Całkowite szczęście to suma szczęścia poszczególnych osób. Jeśli osoba o wartości szczęścia $w$ znajduje się na linii prostej utworzonej przez środki dwóch filiżanek, jej szczęście jest równe $w$. W przeciwnym razie jej szczęście wynosi zero. Ponieważ całkowite szczęście może być duże, wyprowadź wynik modulo 998 244 353.

Napisz program, który będzie śledził całkowite szczęście uczestników!

Wejście

Pierwsza linia zawiera dwie liczby całkowite $N$ oraz $Q$ ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$).

Następna linia zawiera $N$ liczb całkowitych, wartości $v_0, v_1, \dots, v_{N-1}$ ($1 \le v_i \le 1\,000\,000$).

Następne $Q$ linii opisuje zdarzenia. Każda linia jest sformatowana jako „1 $k_i$” ($1 \le k_i \le N$), co oznacza, że platforma obraca się o $k_i \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara, lub „2 $q_i$ $k_i$” ($0 \le q_i < N$, $1 \le k_i \le N$), co oznacza, że filiżanka znajdująca się aktualnie w pozycji $q_i \cdot \frac{360}{N}$ stopni (od góry) obraca się o $k_i \cdot \frac{360}{N}$ stopni zgodnie z ruchem wskazówek zegara wokół swojego środka.

Wyjście

Wyprowadź $Q + 1$ linii, z których każda zawiera całkowite szczęście po 0, 1, 2, \dots, $Q$ zdarzeniach.

Pamiętaj, aby wyprowadzić szczęście modulo 998 244 353.

Przykład

Wejście 1

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

Wyjście 1

189
168
210
252