Cerința

Se dă un string S format doar din litere mici ale alfabetului englez și Q operații de forma:

• 1 a b len – se va afișa 1 dacă secvențele S[a, a+len-1] și S[b, b+len-1] sunt egale. În caz contrar, se va afișa 0.
• 2 l r ch – toate caracterele între pozițiile l și r devin ch.

Să se scrie un program care poate efectua aceste operații.

Date de intrare

Pe prima linie se va afla string-ul S.

Pe a doua linie se va afla numărul Q.

Pe următoarele Q linii se vor afla operațiile.

Date de ieșire

Pentru fiecare operație de tip 1, se va afisa câte un bit 1 dacă dacă secvențele S[a, a+len-1] și S[b, b+len-1] sunt egale. În caz contrar, se va afișa 0.

Restricții și precizări

• Se recomandă folosirea fastio
• 1 ≤ |S| ≤ 100.000
• 1 ≤ Q ≤ 100.000
• 1 ≤ a ≤ b ≤ |S|
• 1 ≤ l, r ≤ |S|
• b+len-1 ≤ |S|
• pentru 20% din teste: 1 ≤ |S| ≤ 1.000, 1 ≤ Q ≤ 1.000
• pentru alte 20% din teste: toate operațiile vor fi de tipul 1
• string-ul este indexat de la 1

Exemplu:

Intrare

asdfiuash
5
1 1 5 1
1 1 7 2
1 1 7 3
2 9 9 d
1 1 7 3

Ieșire

0101

Explicație

Pentru primul caz, comparăm substring-urile "a" și "i". Acestea nu sunt egale.

Pentru al doilea caz, comparăm substring-urile "as" și "as". Acestea sunt egale.

Pentru al treilea caz, comparăm substring-urile "asd" și "ash". Acestea nu sunt egale.

Pentru al patrulea caz, comparăm substring-urile "asd" și "asd". Acestea sunt egale.