410764: GYM104099 2 Праздничная делимость
Description
Недавно Даниил участвовал в командной олимпиаде. В почетном дипломе третьей степени он обнаружил массив $$$a$$$, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, а также число $$$k$$$.
После этого он решил поиграть с обнаруженным массивом. Для этого мальчик $$$q$$$ раз изменяет некоторый элемент массива. Каждое изменение характеризуется двумя числами $$$x$$$ и $$$y$$$, которые означают, что Даниил заменяет элемент массива на позиции $$$x$$$ (который раньше был равен $$$a_x$$$) на число $$$y$$$.
После каждого изменения Даниил хочет посчитать количество таких пар $$$(l, r)$$$, что $$$1 \le l < r \le n$$$ и сумма $$$(a_l + a_r)$$$ делится на $$$k$$$ без остатка. Сейчас мальчик празднует по поводу получения диплома, поэтому не способен решить эту задачу сам.
Входные данныеПервая строка содержит три целых числа $$$n$$$, $$$q$$$ и $$$k$$$ ($$$1 \le n, q \le 100\,000$$$, $$$1 \le k \le 10^9$$$) — размер массива, количество изменений, а также число $$$k$$$ из условия задачи.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.
Каждая из следующих $$$q$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le 10^9$$$) — описание очередного изменения, произведенного Даниилом. После этого изменения число, находящееся на позиции $$$x_i$$$ в массиве заменяется на число $$$y_i$$$.
Выходные данныеВыведите $$$q$$$ строк. В $$$i$$$-й строке выведите одно целое число — количество пар чисел $$$(l, r)$$$, таких что $$$1 \le l < r \le n$$$ и $$$(a_l + a_r)$$$ делится на $$$k$$$ без остатка, после применения первых $$$i$$$ операций.
Система оценкиБаллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | — | полная |
| 1 | 10 | $$$n \le 100$$$, $$$q \le 100$$$ | — | первая ошибка |
| 2 | 20 | $$$n \le 5\,000$$$, $$$q \le 5\,000$$$ | 1 | первая ошибка |
| 3 | 20 | $$$q \le 1\,000$$$, $$$k \le 1\,000$$$ | — | первая ошибка |
| 4 | 12 | $$$k \le 100\,000$$$ | 3 | первая ошибка |
| 5 | 38 | Нет дополнительных ограничений | 1 — 4 | первая ошибка |
5 3 3 1 2 3 4 5 1 3 3 1 2 5Выходные данные
3 4 4Примечание
В изначальном массиве из примера подходящими парами $$$(l, r)$$$ являются $$$(1, 2)$$$: $$$1 + 2 = 3$$$, $$$(1, 5)$$$: $$$1 + 5 = 6$$$, $$$(2, 4)$$$: $$$2 + 4 = 6$$$ и $$$(4, 5)$$$: $$$4 + 5 = 9$$$
После первого изменения массив выглядит следующим образом: $$$3, 2, 3, 4, 5$$$. Подходящими парами в нём являются $$$(1, 3)$$$: $$$3 + 3 = 6$$$, $$$(2, 4)$$$: $$$2 + 4 = 6$$$ и $$$(4, 5)$$$: $$$4 + 5 = 9$$$
После второго изменения массив выглядит следующим образом: $$$3, 2, 1, 4, 5$$$. Подходящими парами в нём являются $$$(2, 3)$$$: $$$2 + 1 = 3$$$, $$$(2, 4)$$$: $$$2 + 4 = 6$$$, $$$(3, 5)$$$: $$$1 + 5 = 6$$$ и $$$(4, 5)$$$: $$$4 + 5 = 9$$$.
После третьего изменения массив выглядит следующим образом: $$$3, 5, 1, 4, 5$$$. Набор подходящих пар не изменится.