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

Від такого нахабства Кормен у гробу перевернувся б!

Д.Е.Кнут

На одній зі станцій "Мотузкового курсу" учасникам пропонується наступне випробування: вони повинні стати в одну лінію на вузьку лавку і, не злізаючи з неї (тобто не торкаючись землі), розвернутися на ній у зворотному порядку.

Незважаючи на те, що це дуже веселий і цікавий конкурс, деякі люди, які вважають його ганебним, стверджують, що насправді його ідея не нова і бере корені з ЛРШ (Літньої Ритуальної Школи). У ЛРШ-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 \leq n \leq 1000000), що складається з малих латинських літер: $i$-й символ описує колір фрака учасника на позиції $i$.

У другому рядку записано єдине число $m$ — кількість подій під час ритуалу (0 \leq m \leq 10000).

У наступних $m$ рядках міститься інформація про події, що відбулися. У кожному з $m$ рядків міститься три числа $t$, $l$ і $r$, які описують подію (t \in \{1, 2\}, 1 \leq l \leq r \leq n). Перше число $t$ описує тип події, що відбувається. Якщо t = 1, то у цей момент ведучий називає числа $l$ і $r$ і лршата на позиціях з $l$-ї по $r$-у стають у зворотному порядку. Якщо t = 2, духи Кнута і Кормена вибирають числа $l$ і $r$ і шепочуть мумії відповідне число $k$.