+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- به یک رشته مثل $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 ```` <details> <summary> **توضیح نمونه ۱** </summary> در درخواست اول تعداد زیررشته‌های جبری `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`). </details>

حل سؤال در بانک سؤالات