Нервных просим условие не читать
Нервных просим условие не читать
От такого нахальства Кормен бы в гробу перевернулся!
Д.Э.Кнут
На одной из станций "Веревочного курса" участникам предлагается следующее испытание: они должны встать в одну линию на узкую скамейку и, не слезая с нее (то есть не касаясь земли), развернуться на ней в обратном порядке.
Несмотря на то, что это очень веселый и интересный конкурс, некоторые люди, считающие его отвратительным, утверждают, что на самом деле его идея не нова и берет корни из ЛРШ (Летней Ритуальной Школы). В ЛРШ-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 (1 ≤ n ≤ 1000000), состоящая из строчных латинских букв: i-й символ описывает цвет сюртука участника на позиции i.
Во второй строке записано единственное число m - количество событий во время ритуала (0 ≤ m ≤ 10000).
В следующих m строках содержится информация о произошедших событиях. В каждой из m строк содержится три числа t, l и r, описывающих событие (t {1, 2}, 1 ≤ l ≤ r ≤ n). Первое число t описывает тип произошедшего события. Если t = 1, то в этот момент ведущий называет числа l и r и лршата на позициях с l-й по r-ю встают в обратном порядке. Если t = 2, духи Кнута и Кормена выбирают числа l и r и нашептывают мумии соответствующее число k.
Выходные данные
Для каждого события типа t = 2 выведите на отдельной строке, сколько раз мумия Дейкстры перевернется в результате невинной забавы духов Кнута и Кормена.
Пример
abacaba 4 1 3 6 1 2 7 2 1 2 2 2 5
2 1