Se dau două numere N și T urmate de un șir de caractere S de lungime N. Se dau apoi T operații de trei 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ța

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 trei 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".