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

---

به یک رشته مثل \(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).