Masala H

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.