F. Инфильтрация инверсий
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$. Изначально $$$a_i = 0$$$ для всех $$$1 \le i \le n$$$.

Перестановка$$$^{\text{∗}}$$$ $$$p$$$ называется корректной, если для каждого $$$1 \le i \le n$$$ выполнено хотя бы одно из следующих условий:

  • $$$a_i = 0$$$.
  • $$$\gcd(p_i, n) = a_i$$$.

Вам нужно обработать $$$q$$$ запросов. В каждом запросе даны два целых числа $$$i$$$ и $$$x$$$, и вы должны перманентно обновить массив, присвоив $$$a_i:= x$$$.

Гарантируется, что в момент каждого запроса $$$a_i = 0$$$, а также что $$$x$$$ делит $$$n$$$.

После выполнения каждого запроса выведите сумму количества инверсий$$$^{\text{†}}$$$ по всем корректным перестановкам. Так как ответы могут быть очень большими, выводите их по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Перестановка длины $$$m$$$ — это массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, а $$$[1,2,2]$$$ не является перестановкой (число $$$2$$$ встречается в массиве дважды), и $$$[1,3,4]$$$ тоже не является перестановкой ($$$m=3$$$, но в массиве есть число $$$4$$$).

$$$^{\text{†}}$$$Инверсия в перестановке $$$p$$$ — это пара индексов $$$(i, j)$$$ такая, что $$$i \lt j$$$ и $$$p_i \gt p_j$$$. Например, перестановка $$$[4, 1, 3, 2]$$$ содержит $$$4$$$ инверсии: $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$ и $$$(3, 4)$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 2 \cdot 10^6$$$; $$$1 \le q \le \min(n, 10^6)$$$) — длину массива $$$a$$$ и количество запросов.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$i$$$ и $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le n$$$).

Гарантируется, что в момент каждого запроса $$$a_i = 0$$$, а также что $$$x$$$ делит $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^6$$$, а сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых чисел — общее количество инверсий по всем корректным перестановкам после обработки каждого запроса.

Так как ответы могут быть большими, выводите их по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
3 2
2 3
3 3
9 3
6 3
7 1
3 3
100 7
67 4
41 25
69 1
99 1
50 100
100 2
9 10
Выходные данные
3
0
1461600
1114560
156960
207622048
432575995
443345156
499213668
665624940
770601684
223944735
Примечание

Для первого набора входных данных изначально $$$a = [0, 0, 0]$$$.

После первого запроса $$$a = [0, 3, 0]$$$. Корректными являются перестановки $$$[1, 3, 2]$$$ и $$$[2, 3, 1]$$$. Общее количество инверсий равно $$$1 + 2 = 3$$$.

После второго запроса $$$a = [0, 3, 3]$$$. Корректных перестановок нет.