Вы находитесь в местном парке аттракционов и наблюдаете за аттракционом «Чашки». Понаблюдав некоторое время, вы замечаете несколько интересных особенностей этого аттракциона.

Аттракцион состоит из $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_i \cdot \frac{360}{N}$ градусов по часовой стрелке. Чашки компенсируют это вращение, поэтому их ориентация относительно внешней стороны платформы не меняется.
• Чашка, находящаяся в данный момент на $q_i \cdot \frac{360}{N}$ градусов по часовой стрелке от севера, поворачивается на $k_i \cdot \frac{360}{N}$ градусов по часовой стрелке вокруг своего центра. Остальные чашки не затрагиваются.

Вы хотите вычислить суммарное счастье всех людей изначально и после каждого события. Общее счастье — это сумма значений счастья отдельных людей. Если человек со значением счастья $w$ находится на прямой, образованной центрами двух чашек, его счастье равно $w$. В противном случае его счастье равно нулю. Поскольку общее счастье может быть большим, выведите его по модулю 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_i$» ($1 \le k_i \le N$), что означает, что платформа поворачивается на $k_i \cdot \frac{360}{N}$ градусов по часовой стрелке, либо как «2 $q_i$ $k_i$» ($0 \le q_i < N$, $1 \le k_i \le N$), что означает, что чашка, находящаяся в данный момент на $q_i \cdot \frac{360}{N}$ градусов (от верха), поворачивается на $k_i \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