Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri:

1. Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului.
2. Se răspunde cu 1 dacă secvenţa de litere care începe la poziţia q1 şi are lungimea lg coincide literă cu literă, cu secvenţa care începe la poziţia q2 şi are aceeaşi lungime lg şi se răspunde cu 0 în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.

Cerința

Fiind dat un şir de N litere mici şi o listă de M operaţii, să se afişeze răspunsurile la operaţiile de tip 2, respectând ordinea din succesiunea de operaţii date.

Date de intrare

Fișierul de intrare diez.in conține pe prima linie valorile N şi M, separate printr-un spaţiu cu semnificaţia din enunţ. Pe a doua linie se află un şir de N litere mici ale alfabetului englez iar următoarele M linii conţin câte o operaţie în unul dintre formatele:

• 1 p x – Datele pentru operaţia de tipul 1.
• 2 q1 q2 lg – Datele pentru operaţia de tipul 2.

Date de ieșire

În fișierul de ieșire diez.out se vor scrie valori egale cu 0 sau 1, câte una pe o linie, reprezentând răspunsurile date, în ordine, la operaţiile de tipul 2 existente în fişierul de intrare.

Restricții și precizări

• 1 ≤ N, M ≤ 250 000
• 0 ≤ p ≤ lungimea şirului la momentul inserării
• x este literă mică a alfabetului englez
• q1, q2 ≥ 0; se garantează că pentru fiecare operaţie de tipul 2 există lg caractere în şir începând atât cu poziţia q1 cât şi cu poziţia q2
• 1 < lg ≤ lungimea şirului la momentul efectuării operaţiei de tipul 2
• Numerotarea caracterelor din şir începe de la poziţia 0

Exemplul 1

diez.in

8 6
abcasfas
2 0 5 3
1 3 d
2 4 7 2
1 1 s
1 10 b
2 0 8 3

diez.out

0
1
1

Explicație

Se compară secvenţele abc şi fas care sunt diferite → se afişează 0
Caracterul d este inserat înainte de poziţia 3 şi se obţine şirul abcdasfas
Se compară subşirurile as şi as, sunt identice → se afişează 1
Caracterul s este inserat înainte de poziţia 1, se obţine şirul asbcdasfas
Caracterul b este inserat pe poziţia 10, poziţia este egală cu lungimea şirului, se obţine şirul asbcdasfasb
Se compară subşirurile asb si asb , sunt identice → se afişează 1

Exemplu:

diez.in

6 3
atmatm
2 0 2 4
1 6 a
2 0 3 4

diez.out

0
1

Explicație

Se compară subşirurile atma şi matm, sunt diferite → se afişează 0
Caracterul a se alipeşte la final, se obţine şirul atmatma
Se compară subşirurile atma atma, sunt identice → se afişează 1