ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2042. Никита

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
После того, как Никита не решил на IOI задачу с запросами на отрезке, он захотел порадовать участников сборов в Петрозаводске другой задачей с запросами на отрезке.
Вам дана строка s и целое число k. Далее даны запросы.
Запросы бывают двух видов:
  1. Для данных чисел l, r и символа c заполнить подстроку s[l..r] символом c.
  2. Для данных l и r выдать число пар i и j таких, что lijr, ji + 1 ≤ k и s[i..j] — палиндром.
Символы в строке нумеруются с единицы.

Исходные данные

В первой строке дана строка s из латинских букв, после которой через пробел расположено целое число k (1 ≤ k ≤ 50). Длина строки не превосходит 105. Во второй строке дано целое число m (1 ≤ m ≤ 105) — количество запросов. В следующих m строках даны запросы. Каждая строка запроса начинается с типа (1 или 2), далее идут числа l, r (1 ≤ lr ≤ |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