Нервових просимо умову не читати
Від такого нахабства Кормен у гробу перевернувся б!
Д.Е.Кнут
На одній зі станцій "Мотузкового курсу" участникам пропонується наступний іспит: вони повинні стати в одну лінію на вузьку лавку і, не злізаючи з неї (тобтоь не дотикаючись землі), розвернутись на ній у зворотному порядку.
Не дивлячись на те, что це дужеь веселий і цікавий конкурс, деякі люди, які вважають його ганебним, стверджують, що насправді його ідея не нова і бере корні з ЛРШ (Літньої Ритуальної Школи). У ЛРШ-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 виведіть у окремому рядку, скільки разів мумія Дейкстри перевернеться в результаті безневинної забавки духів Кнута та Кормена.