sufixe

Se dau două numere N și T urmate de un șir de caractere S de lungime N. Se dau apoi T operații de 3 tipuri:

1. Se adaugă un caracter la sfârșitul șirului S;
2. Se adaugă șirul S în mulțimea M doar dacă acesta nu există deja în mulțime;
3. Se cere numărul de șiruri din mulțimea M care sunt sufixe ale șirului S;

Cerinţă

Afișați răspunsul tuturor operațiilor de tip 3.

Date de intrare

Pe prima linie din fișierul sufixe.in se află două numere naturale N și T.
Pe a doua linie din fișierul de intrare se află șirul S.
Fiecare dintre următoarele T linii va conține tipul uneia dintre cele 3 operații. Pe aceeași linie cu operația 1 se va găsi un caracter a..z;

Date de ieșire

Fişierul de ieşire sufixe.out va conţine răspunsul operațiilor de tip 3, cate unul pe fiecare linie

Restricții și precizări

• 1 ≤ N ≤ 1 000
• 1 ≤ T ≤ 1 200 000
• Inițial mulțimea M este vidă.

Exemplu

sufixe.in

1 11
a
2
1 b
1 a
2
2
1 c
1 a
3
1 b
1 a
3

sufixe.out

1
2

Explicație

Pornim cu șirul inițial S=“a”.
Adăugăm șirul S=“a” la mulțimea M => M={“a”};
Adăugăm șirului S caracterul b și obținem S=“ab”.
Adăugăm șirului S caracterul a și obținem S=“aba”.
Adăugăm șirul S=“aba” la mulțimea M => M={“a”, “aba”};
Adăugăm șirul S=“aba” la mulțimea M => M={“a”, “aba”};
Adăugăm șirului S caracterul c și obținem S=“abac”.
Adăugăm șirului S caracterul a și obținem S=“abaca”.
Rezultatul operației 3 este 1 : a.
Adăugăm șirului S caracterul b și obținem S=“abacab”.
Adăugăm șirului S caracterul a și obținem S=“abacaba”.
Rezultatul operației 3 este 2: a, aba.