Праздничная делимость

Мише на день рождения подарили массив a1, a2, . . . , an, состоящий из n целых положительных
чисел.
Мише надоело, что ему каждый год дарят массивы, поэтому он решил его изменить. Мальчик
решил произвести q изменений следующего вида: «Заменить число, находящееся на позиции xi на
число yi».
После каждой операции изменения Миша хочет знать, сколько существует таких пар чисел (l, r),
что l < r и al + ar делится на k без остатка. Так как Миша не силен в математике и устном счете,
вам предстоит помочь ему и решить данную задачу.
Формат входных данных
Первая строка содержит три целых числа n, q и k (1 6 n, q 6 100 000, 1 6 k 6 109
) — количество
элементов в массиве, количество изменений, которые хочет сделать Миша, а также число, на которое
должна делиться сумма чисел в искомых парах, соответственно.
Вторая строка содержит n целых чисел a1, a2, . . . , an (1 6 ai 6 109
) — элементы массива.
Каждая из следующих q строк содержит два целых числа xi и yi (1 6 xi 6 n, 1 6 yi 6 109
) —
описание очередного изменения, произведенного Мишей. После этого изменения число, находящееся
на позиции xi в массиве заменяется на число yi
.
Формат выходных данных
Выведите q строк. В i-й строке одно целое число — количество пар чисел (l, r), таких что l < r
и al + ar делится на k без остатка после применения первых i операций.
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
Ввод
5 3 3
1 2 3 4 5
1 3
3 1
2 5
Вывод
3
4
4

0