Masala #HYVD5EQYMD

Sizga bir sirli satr \(s\) berilgan. Ushbu satr o'z ichiga qiziqarli belgilarni oladi va SamCoding jamoasi sizdan u ustida bir nechta so'rovlarga javob berishni talab qiladi. Satr bilan ishlash uchun sizga \(q\) ta so'rov beriladi, har bir so'rov quyidagi ikki turdan biriga tegishli:

1-tur: “Belgini almashtirish”

So'rov \(1 \space{} i  \space{} c  \space{} -\) ko'rinishida berilsa \(s\) satrning \(i-\)pozitsiyadagi joylashgan belgini \(c\) ga almashtirish kerak.

2-tur: “Substring izlash”

So'rov \(2 \space{} l  \space{} r  \space{} y  \space{} -\) ko'rinishida berilsa \(s_l + s_{l+1}+... +s_r\) satr ichida \(y\) substringi necha marta uchrashini hisoblash kerak.

Substring – bu berilgan satrning ketma-ket tartibda keladigan qismidir (“abc” satrning barcha substringlari “a”, “b”, “c”, “ab”, “bc” va “abc”).

Kirish faylining dastlabki satrida \(s(1\leq |s|\leq 100000,s_i\in [a,b,...,z])\) satr beriladi. 

Kiyingi satrda so'rovlar soni \(q(1\leq q\leq 100000)\) beriladi. 

Kiyingi \(q\) ta satrda yuqorida aytib o'tilgan ikki turga mansub so'rovlar beriladi.

• \(1,i,c(1\leq i\leq |s|, c\in[a,b,...,z])\);
• \(2,l,r,y(1\leq l\leq r\leq |s|, 1\leq |y|\leq 10^5)\);

Barcha so'rovlar uchun \(|y|\) larning yig'indisi \(10^5\) dan oshmasligi kafolatlanadi

Chiqish faylida har bir ikkinchi turga mansub so'rovga javobni alohida satrlarda chop eting.