Задача C. Кратные суммы

Автор:Женя Татаринов, Исмаил Велиджанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

У Анжелики есть массив натуральных чисел a, длина которого равна n, а также у Анжелики есть любимое число, равное s. Жене очень нравится этот массив, поэтому он просит Анжелику проводить над данным массивом операции. Всего Женя попросит Анжелику выполнить q операций. Каждая операция имеет один из двух видов:

Так как Женя очень надоедливый и хочет спросить Анжелику очень много раз, Анжелика скинула эту работу на Вас! Помогите Анжелике!

Формат входных данных

В первой строке вводятся натуральные числа n, s и q — длина массива, любимое число Анжелики и количество операций соответственно (1 ≤ n, q ≤ 50000, 2 ≤ s ≤ 50). В следующей строке вводится массив Анжелики (1 ≤ ai ≤ 109).

В последующих q строках вводятся запросы Жени. Если первое число в строке равно 1, то после него следуют числа k и d, это означает, что Женя хочет изменить значение ak на d. Если первое число в строке равно 2, то после него ничего не следует, это означает, что Женя хочет узнать количество пар чисел l и r таких, что 1 ≤ l ≤ r ≤ n и сумма al + al + 1 + ...  + ar − 1 + ar кратна s.

Гарантируется, что существует хотя бы один запрос второго вида, а также гарантируется, что в любой момент любое число из массива Анжелики является натуральным числом, не большим 109.

Формат выходных данных

Для каждого запроса второго вида на отдельной строке выведите количество подходящих пар чисел l и r.

Примеры тестов

Стандартный вход Стандартный выход
1
4 3 5
1 2 1 2
2
1 2 1
2
1 2 3
2
4
2
3

0.073s 0.014s 13