После того, как Никита не решил на IOI задачу с запросами на отрезке, он захотел порадовать участников сборов в Петрозаводске другой задачей с запросами на отрезке.
Вам дана строка s и целое число k. Далее даны запросы.
Запросы бывают двух видов:
- Для данных чисел l, r и символа c заполнить подстроку s[l..r] символом c.
- Для данных l и r выдать число пар i и j таких, что l ≤ i ≤ j ≤ r, j − i + 1 ≤ k и s[i..j] — палиндром.
Символы в строке нумеруются с единицы.
Исходные данные
В первой строке дана строка s из латинских букв, после которой через пробел расположено целое число k (1 ≤ k ≤ 50). Длина строки не превосходит 105.
Во второй строке дано целое число m (1 ≤ m ≤ 105) — количество запросов.
В следующих m строках даны запросы. Каждая строка запроса начинается с типа (1 или 2), далее идут числа l, r (1 ≤ l ≤ r ≤ |s|). Далее для запросов первого типа следует символ c — строчная латинская буква.
Результат
На каждый запрос второго типа выведите целое число в отдельной строке.
Пример
исходные данные | результат |
---|
abacaba 4
3
2 1 3
1 1 3 c
2 1 4
| 4
10
|
Автор задачи: Никита Сивухин
Источник задачи: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014