당신은 지역 놀이공원에서 회전하는 찻잔 놀이기구를 발견하고, 이 놀이기구에 대한 몇 가지 흥미로운 점을 관찰했습니다.

이 놀이기구는 회전판 둘레에 동일한 간격으로 배치된 $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 \cdot \frac{360}{N}$도 회전합니다. 찻잔들은 이를 보상하여 외부를 기준으로 한 방향이 영향을 받지 않도록 합니다.
• 현재 북쪽에서 시계 방향으로 $q \cdot \frac{360}{N}$도인 지점에 있는 찻잔이 중심을 기준으로 시계 방향으로 $k \cdot \frac{360}{N}$도 회전합니다. 다른 찻잔들은 영향을 받지 않습니다.

당신은 초기 상태와 매 이벤트가 발생한 후 모든 사람의 총 행복도를 계산하고자 합니다. 총 행복도는 각 개인의 행복도의 합입니다. 행복도 값 $w$를 가진 사람이 두 찻잔의 중심을 잇는 직선 위에 있다면, 그 사람의 행복도는 $w$입니다. 그렇지 않으면 행복도는 0입니다. 총 행복도는 매우 클 수 있으므로 $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$” ($1 \le k \le N$) 형식으로, 회전판이 시계 방향으로 $k \cdot \frac{360}{N}$도 회전함을 나타내거나, “2 $q$ $k$” ($0 \le q < N$, $1 \le k \le N$) 형식으로, 현재 (위쪽에서) $q \cdot \frac{360}{N}$도 지점에 있는 찻잔이 중심을 기준으로 시계 방향으로 $k \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