Masala H

Xotira 32 MB Vaqt 1000 ms
14

Satr ichidagi sarguzashtlar

Sizga bir sirli satr ss 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 qq ta so'rov beriladi, har bir so'rov quyidagi ikki turdan biriga tegishli:

1-tur: “Belgini almashtirish”

So'rov 1 i  c  1 \space{} i  \space{} c  \space{} - ko'rinishida berilsa ss satrning ii-pozitsiyadagi joylashgan belgini cc ga almashtirish kerak.

2-tur: “Substring izlash”

So'rov 2 l  r  y  2 \space{} l  \space{} r  \space{} y  \space{} - ko'rinishida berilsa sl+sl+1+...+srs_l + s_{l+1}+... +s_r satr ichida yy 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”).


Kiruvchi ma'lumotlar:

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

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

Kiyingi qq ta satrda yuqorida aytib o'tilgan ikki turga mansub so'rovlar beriladi.

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

Barcha so'rovlar uchun y|y| larning yig'indisi 10510^5 dan oshmasligi kafolatlanadi


Chiquvchi ma'lumotlar:

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


Misollar
# input.txt output.txt
1
ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba
3
1