\textit{От такого нахальства Кормен бы в гробу перевернулся!} \textit{Д.Э.Кнут} На одной из станций "Веревочного курса" участникам предлагается следующее испытание: они должны встать в одну линию на узкую скамейку и, не слезая с нее (то есть не касаясь земли), развернуться на ней в обратном порядке. Несмотря на то, что это очень веселый и интересный конкурс, некоторые люди, считающие его отвратительным, утверждают, что на самом деле его идея не нова и берет корни из ЛРШ (Летней Ритуальной Школы). В ЛРШ-1910 уверовали, что для закрепления знаний алгоритмов на строках, необходимо собираться ночью и танцевать на гробе, в котором лежит мумия Дейкстры. Ученики ЛРШ-1910 верили, что для достижения нужного эффекта совершенно необходимо было надеть сюртуки, выдаваемые в предыдущих сменах. Так как в \textbf{1910} году ЛРШ проводилась в \textbf{27}-й раз, у всех учеников была возможность надеть один из \textbf{26} сюртуков, выданных в прошлые разы. Забавно, но за \textbf{26} лет в ЛРШ ни разу не повторились с цветами выдаваемых сюртуков. Поэтому к моменту начала ритуала все лршата были одеты в сюртуки одного из \textbf{26} цветов. Ритуальный танец выглядел следующим образом. Все участники вставали на гроб в один ряд. На земле оставался только ведущий, руководивший танцем. Время от времени он называл два числа \textbf{l} и \textbf{r} - порядковые номера каких-то танцующих. После этого все участники ритуала с порядковыми номерами с \textbf{l}-й по \textbf{r}-й включительно должны были встать в обратном порядке, то есть на позиции \textbf{l} после этого должен был оказаться тот, кто был на \textbf{r}-й позиции, на \textbf{(l+1)}-й позиции - участник с \textbf{(r-1)}-й позиции и так далее. Легенда гласит, что во время ЛРШ-1910 за этим ритуалом наблюдали духи Кнута и Кормена. Время от времени забавы ради они выбирали позиции \textbf{l} и \textbf{r}. Затем они находили самое большое \textbf{k}, такое что для всех \textbf{i} от \textbf{0} до \textbf{k-1 }включительно цвета сюртуков лршат на позициях \textbf{l+i} и \textbf{r+i} совпадали. Потом они подлетали к гробу и шептали полученное \textbf{k} на ухо мумии. Узнав о таком нахальстве, мумия Дейкстры в ярости переворачивалась в гробу ровно\textbf{k} раз. Сейчас на дворе 2010-й год, и противники конкурса на скамейке хотят привести неопровержимые доказательства того, что этот конкурс отвратителен, и Дейкстре бы не понравился. Но для того, чтобы это доказать, им надо сперва проанализировать его переворачивания в ЛРШ-1910. Помогите им и скажите, сколько раз переворачивалась мумия Дейкстры во время ритуала. \InputFile В первой строке входного файла содержится информация о начальном расположении участников ритуала на гробе - строка длины \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000000}), состоящая из строчных латинских букв: \textbf{i}-й символ описывает цвет сюртука участника на позиции \textbf{i}. Во второй строке записано единственное число \textbf{m} - количество событий во время ритуала (\textbf{0} ≤ \textbf{m} ≤ \textbf{10000}). \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} В следующих \textbf{m} строках содержится информация о произошедших событиях. В каждой из \textbf{m} строк содержится три числа \textbf{t}, \textbf{l} и \textbf{r}, описывающих событие (\textbf{t} \{\textbf{1}, \textbf{2}\}, \textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{n}). Первое число \textbf{t} описывает тип произошедшего события. Если \textbf{t = 1}, то в этот момент ведущий называет числа \textbf{l} и \textbf{r} и лршата на позициях с \textbf{l}-й по \textbf{r}-ю встают в обратном порядке. Если \textbf{t = 2}, духи Кнута и Кормена выбирают числа \textbf{l} и \textbf{r} и нашептывают мумии соответствующее число \textbf{k}. \OutputFile Для каждого события типа \textbf{t = 2} выведите на отдельной строке, сколько раз мумия Дейкстры перевернется в результате невинной забавы духов Кнута и Кормена.