eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Нервных просим условие не читать

Нервных просим условие не читать

Лимит времени 8 секунд
Лимит использования памяти 64 MiB

От такого нахальства Кормен бы в гробу перевернулся!

Д.Э.Кнут

На одной из станций "Веревочного курса" участникам предлагается следующее испытание: они должны встать в одну линию на узкую скамейку и, не слезая с нее (то есть не касаясь земли), развернуться на ней в обратном порядке.

Несмотря на то, что это очень веселый и интересный конкурс, некоторые люди, считающие его отвратительным, утверждают, что на самом деле его идея не нова и берет корни из ЛРШ (Летней Ритуальной Школы). В ЛРШ-1910 уверовали, что для закрепления знаний алгоритмов на строках, необходимо собираться ночью и танцевать на гробе, в котором лежит мумия Дейкстры.

Ученики ЛРШ-1910 верили, что для достижения нужного эффекта совершенно необходимо было надеть сюртуки, выдаваемые в предыдущих сменах. Так как в 1910 году ЛРШ проводилась в 27-й раз, у всех учеников была возможность надеть один из 26 сюртуков, выданных в прошлые разы. Забавно, но за 26 лет в ЛРШ ни разу не повторились с цветами выдаваемых сюртуков. Поэтому к моменту начала ритуала все лршата были одеты в сюртуки одного из 26 цветов.

Ритуальный танец выглядел следующим образом. Все участники вставали на гроб в один ряд. На земле оставался только ведущий, руководивший танцем. Время от времени он называл два числа l и r - порядковые номера каких-то танцующих. После этого все участники ритуала с порядковыми номерами с l-й по r-й включительно должны были встать в обратном порядке, то есть на позиции l после этого должен был оказаться тот, кто был на r-й позиции, на (l+1)-й позиции - участник с (r-1)-й позиции и так далее.

Легенда гласит, что во время ЛРШ-1910 за этим ритуалом наблюдали духи Кнута и Кормена. Время от времени забавы ради они выбирали позиции l и r. Затем они находили самое большое k, такое что для всех i от 0 до k-1 включительно цвета сюртуков лршат на позициях l+i и r+i совпадали. Потом они подлетали к гробу и шептали полученное k на ухо мумии. Узнав о таком нахальстве, мумия Дейкстры в ярости переворачивалась в гробу ровноk раз.

Сейчас на дворе 2010-й год, и противники конкурса на скамейке хотят привести неопровержимые доказательства того, что этот конкурс отвратителен, и Дейкстре бы не понравился. Но для того, чтобы это доказать, им надо сперва проанализировать его переворачивания в ЛРШ-1910.

Помогите им и скажите, сколько раз переворачивалась мумия Дейкстры во время ритуала.

Входные данные

В первой строке входного файла содержится информация о начальном расположении участников ритуала на гробе - строка длины n (1n1000000), состоящая из строчных латинских букв: i-й символ описывает цвет сюртука участника на позиции i.

Во второй строке записано единственное число m - количество событий во время ритуала (0m10000).

В следующих m строках содержится информация о произошедших событиях. В каждой из m строк содержится три числа t, l и r, описывающих событие (t {1, 2}, 1lrn). Первое число t описывает тип произошедшего события. Если t = 1, то в этот момент ведущий называет числа l и r и лршата на позициях с l-й по r-ю встают в обратном порядке. Если t = 2, духи Кнута и Кормена выбирают числа l и r и нашептывают мумии соответствующее число k.

Выходные данные

Для каждого события типа t = 2 выведите на отдельной строке, сколько раз мумия Дейкстры перевернется в результате невинной забавы духов Кнута и Кормена.

Пример

Входные данные #1
abacaba
4
1 3 6
1 2 7
2 1 2
2 2 5
Выходные данные #1
2
1
Автор А.Банных, В.Фондаратов