Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В волшебной книге Виллины записано число из `N` цифр, с которым волшебница проделывает 2 вида экспериментов.
Во-первых, Виллина может разом заменить все цифры с номерами от `L` до `R` включительно на цифру `C`.
Во-вторых, Виллина может сделать заклинание из цифр с номерами от `L` до `R`, не меняя их порядка. Чтобы определить
силу получившегося заклинания, нужно рассмотреть все его непустые подстроки. Каждая подстрока, образующая число,
кратное магическому числу `K`, увеличивает силу заклинания на 1. Число-подстрока
может совпадать с целой строкой, а также иметь ведущие нули (все такие числа учитываются, если они кратны `K`).
Помогите Виллине предсказать заранее силу всех полученных заклинаний.
В первой строке ввода находятся три натуральных числа: `N` – количество цифр в книге (`1<=N<=10^5`), `Q` – количество
экспериментов (`1<=Q<=10^4`) и магическое число `K` (`2<=K<=10`).
Следующая строка состоит из `N` цифр без пробелов, описывающих начальное состояние книги.
Затем следует `Q` строк, описывающих эксперименты в порядке их проведения.
Эксперименты-замены описываются как "`1 \quad L \quad R \quad C`" (`1<=L<=R<=N`, `0<=C<=9`);
Эксперименты-заклинания записываются как "`2 \quad L \quad R`" (`1<=L<=R<=N`).
Для каждого из экспериментов-заклинаний выведите одно число — силу полученного заклинания.
```sample Пример ввода
5 6 3
60311
2 1 3
2 4 5
1 3 4 2
2 4 5
2 1 5
2 2 2
```
```sample Пример вывода
6
0
1
4
1
```
Пояснение к примеру:
- в первом запросе строка "603" включает 6 подстрок: "6", "0", "3", "60", "03", "603" - все они образуют числа, кратные 3;
- во втором запросе строка "11" не содержит не одной подходящей подстроки;
- после третьего запроса строка приобретает вид "60221";
- в четвертом запросе строка "21" содержит ровно одну подходящую подстроку - себя саму;
- в пятом запросе учитываются подстроки "6", "0", "60", "21";
- в шестом запросе учитывается единственная подстрока "0".
Начало
Рабочее место участника
Дерево отрезков, декартово дерево, √-декомпозиция