Автор: | Женя Татаринов, Исмаил Велиджанов | Ограничение времени: | 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 |
|
|