trei

Se dă o listă cu $n$ cuvinte și $q$ operații pe această listă. Pot exista aceleași cuvinte de mai multe ori în listă.

Operațiile sunt următoarele:

• 1 s - Adaugă cuvântul $s$ în listă.
• 2 s - Șterge o apariție a cuvântului $s$ din listă. Dacă acel cuvânt nu se află în listă, nu se întâmplă nimic.
• 3 s - Află numărul de triplete distincte formate din cuvinte din listă care au ca sufix cuvântul $s$.

Cerință

Efectuați pe rând toate operațiile. Afișați răspunsurile la operațiile de tip 3.

Date de intrare

De pe prima linie se citește numărul natural $n$, iar de pe a doua linie se citesc elementele listei descrise în enunț, separate prin exact un spațiu.
Pe următoarea linie se citește numărul natural $q$, iar pe următoarele linii se citesc operațiile descrise în enunț.

Date de ieșire

Pe fiecare linie, se afișează răspunsurile la operațiile de tip 3.

Restricții și precizări

• Pentru 20 de puncte, $0 \leq n, q \leq 1.000$.
• Pentru încă 25 de puncte, $0 \leq n, q \leq 100.000$.
• Pentru încă 55 de puncte, $0 \leq n, q \leq 1.000.000$. Pentru submisii în C++, este recomandată includerea acestei linii de cod la începutul funcției main(): cin.tie(0);ios::sync_with_stdio(0);.
• Distincția dintre triplete se face prin pozițiile cuvintelor în listă, nu prin conținutul cuvintelor.
• Fiecare cuvânt din datele de intrare va avea minim un caracter și maxim 20 de caractere. Caracterele permise sunt doar cele 26 litere mici de la a la z.

Exemplu

stdin

5
acasa sa sa sa casa
3
2 sa
3 a
3 casa

stdout

4
0

Explicație

• După operația 2 sa, s-a șters din listă o apariție a cuvântului sa. Acum, lista este formată din cuvintele acasa, sa, sa, casa.
• Operația 3 a va afișa numărul 4, deoarece tripletele formate din cuvinte care au ca sufix cuvântul a sunt (acasa,sa,sa), (acasa,sa,casa), (acasa,sa,casa) și (sa,sa,casa). Motivul pentru care (acasa,sa,casa) a fost numărat de două ori este pentru că în primul triplet am considerat cuvântul sa de pe poziția 2 în listă, iar în al doilea triplet am considerat cuvântul sa de pe poziția 3 în listă.
• Operația 3 casa va afișa numărul 0, deoarece singurele cuvinte care au ca sufix cuvântul casa sunt cuvintele acasa și casa, acestea neputând forma un triplet.