행복도

당신은 동네 놀이공원에서 회전하는 찻잔 놀이기구를 보고 있습니다. 잠시 관찰하면 이 놀이기구에 대해 몇 가지 흥미로운 점이 보입니다.

이 놀이기구는 회전판 둘레에 같은 간격으로 놓인 $N$개의 원형 찻잔으로 이루어집니다. $i = 0, 1, \ldots, N - 1$에 대해 $i$번째 찻잔의 중심은 처음에 북쪽에서 시계 방향으로 $i \cdot \frac{360}{N}$도 떨어진 점에 있습니다. 회전판은 찻잔들이 서로 부딪히지 않을 만큼 충분히 큽니다. 각 찻잔에는 $N$명의 사람이 찻잔 둘레에 같은 간격으로 앉아 있습니다. $i = 0, 1, \ldots, N - 1$에 대해 $i$번째 사람은 처음에 북쪽에서 시계 방향으로 $i \cdot \frac{360}{N}$도 떨어진 점에 있습니다. 찻잔이 충분히 크므로 사람은 점으로 봅니다. 각 찻잔에서 $i$번째 사람의 행복 값은 $v_i$입니다. 서로 다른 찻잔에서 처음 같은 위치에 있는 사람들은 같은 행복 값을 갖습니다.

$Q$밀리초 동안 매 밀리초마다 다음 두 사건 중 하나가 일어납니다.

• 회전판이 시계 방향으로 $k_i \cdot \frac{360}{N}$도 회전합니다. 찻잔들은 이를 보상하므로, 회전판 바깥을 기준으로 한 찻잔의 방향은 바뀌지 않습니다.
• 북쪽에서 시계 방향으로 $q_i \cdot \frac{360}{N}$도 떨어진 위치에 있는 찻잔이 자신의 중심을 기준으로 시계 방향으로 $k_i \cdot \frac{360}{N}$도 회전합니다. 다른 찻잔은 영향을 받지 않습니다.

처음과 매 사건 뒤의 모든 사람의 행복도 합을 구하세요. 총 행복도는 개인 행복 값의 합입니다. 행복 값이 $w$인 사람이 두 찻잔의 중심을 잇는 직선 위에 있으면 그 사람의 행복도는 $w$입니다. 그렇지 않으면 0입니다. 총 행복도는 클 수 있으므로 998244353으로 나눈 나머지를 출력하세요.

첫 줄에 두 정수 $N$, $Q$ ($2 \le N \le 200000$, $1 \le Q \le 200000$)가 주어집니다.

다음 줄에는 $N$개의 정수 $v_0, v_1, \ldots, v_{N-1}$ ($1 \le v_i \le 1000000$)이 주어집니다.

다음 $Q$개의 줄은 사건을 나타냅니다. 각 줄은 "1 $k_i$" ($1 \le k_i \le N$) 형식이거나 "2 $q_i$ $k_i$" ($0 \le q_i < N$, $1 \le k_i \le N$) 형식입니다. 첫 번째 형식은 회전판이 시계 방향으로 $k_i \cdot \frac{360}{N}$도 회전한다는 뜻입니다. 두 번째 형식은 위쪽(북쪽)에서 시계 방향으로 $q_i \cdot \frac{360}{N}$도 떨어진 찻잔이 자신의 중심을 기준으로 시계 방향으로 $k_i \cdot \frac{360}{N}$도 회전한다는 뜻입니다.

$Q+1$개의 줄을 출력합니다. $j$번째 줄 ($j = 0, 1, \ldots, Q$)에는 $j$개의 사건을 처리한 뒤의 총 행복도를 998244353으로 나눈 나머지로 씁니다.