\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} виведіть у окремому рядку, скільки разів мумія Дейкстри перевернеться в результаті безневинної забавки духів Кнута та Кормена.