• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

---

به یک رشته مثل $s$ یک جمله‌ی جبری می‌گوییم هرگاه فقط از بتوان آن را به دو قسمت مثل $ab$ تقسیم کرد که $a$ یک عدد طبیعی و $b$ رشته‌ای از حروف کوچک انگلیسی باشد. برای مثال رشته‌های 3x و 115ali عبارت جبری هستند ولی 1x2y ،12 و xy عبارت جبری نیستند.

حال به شما یک رشته به طول $n$ مثل $s$ از حروف کوچک انگلیسی (کاراکترهای a تا z) و ارقام (کاراکترهای 1 تا 9) داده می‌شود و از شما $q$ درخواست می‌شود، در خواست‌ها دو نوع دارند:

• در درخواست نوع اول، دو عدد $l$ و $r$ که $1 \leq l \leq r \leq n$ است داده می‌شود و تعداد زیررشته‌های متوالی $s_l, s_{l+1}, \dots, s_r$ آن که عبارت جبری هستند را چاپ کنید.
• در درخواست نوع دوم، عدد $i$ و کاراکتر $c$ به شما داده می‌شود و از شما می‌خواهیم $s_i$ را به $c$ تغییر دهید.

منظور از زیررشته‌ی متوالی یک رشته مثل $s$، رشته‌ای است که از حذف کردن تعدادی (حتی صفر) کاراکتر از ابتدا و انتهای آن بدست بیاید. برای مثال ode، cup زیررشته‌ی متوالی codecup است ولی ccup و puc زیررشته‌ی متوالی آن نیست.

ورودی

در سطر اول دو عدد صحیح و مثبت $n$ و $q$ داده می‌شود. $$1 \leq n, q \leq 200 , 000$$

در سطر دوم ورودی رشته‌ی $s$ شامل $n$ کاراکتر از حروف کوچک و ارقام به طول $n$ داده می‌شود. در ‌$q$ سطر بعدی در هر سطر یا سه عدد 1 و $l$ و $r$ داده می‌شود که نشان دهنده‌ی درخواستی از نوع اول است.

$$1 \leq l \leq r \leq n$$

یا دو عدد 2 و $i$ و کاراکتر c داده می‌شود که نشان دهنده‌ی درخواست نوع دوم است.

$$1 \leq i \leq n$$ $$c \in {a, b, \dots, z, 1, 2, \dots, 9}$$

خروجی

در سطرهای جداگانه، به ترتیب پاسخ پاسخ درخواست‌های نوع اول را چاپ کنید. تضمین می‌شود حداقل یک درخواست از نوع اول وجود دارد.

مثال‌ها

ورودی نمونه ۱

10 6
183xa11u7z
1 1 5
2 2 x
1 1 5
1 5 9
2 9 8
1 1 10

خروجی نمونه ۱

6
3
2
6

توضیح نمونه ۱

در درخواست اول تعداد زیررشته‌های جبری 183xa پرسیده شده که برابر ۶ است (3x، 3xa، 83x، 83xa، 183x و 183xa).

در درخواست دوم رشته‌ی $s$ به 1x3xa11u7z تبدیل می‌شود.

در درخواست سوم تعداد زیررشته‌های جبری 1x3xa پرسیده شده که برابر ۳ است (1x، 3x و 3xa).

در درخواست چهارم تعداد زیررشته‌های جبری a11u7 پرسیده شده که برابر ۲ است (1u و 11u).

در درخواست پنجم رشته‌ی $s$ به 1x3xa11u9z تبدیل می‌شود.

در درخواست ششم تعداد زیررشته‌های جبری 1x3xa11u9z پرسیده شده که برابر ۶ است (1x، 3x، 3xa، 1u، 11u و 9z).