Conflicte

Enunț

RAU-Gigel își amintește cu nostalgie de momentele sale de început într-ale programării, când mai făcea și stângăcii cum ar fi să declare un nume de tipul int.... așa a apărut următoarea problemă: Să ne imaginăm harta politică a lumii viitorului, împărțită în țări ale căror nume sunt de fapt numere naturale nenule. Între ele există anumite relații: două țări sunt înfrățite dacă au în compunerea numelui lor aceleași cifre (nu contează numărul de apariții), în timp ce două țări se află în conflict dacă nu au nicio cifră comună în numele lor. Interesat de politică, RAU-Gigel ar vrea să afle câteva informații:

• întrebare de tipul $1$: câte țări sunt neutre din punct de vedere politic, în sensul că nu sunt înfrățite cu nicio altă țară?
• întrebare de tipul $2$: pentru fiecare țară dintr-o listă de țări preferate să se afle: cu câte țări este înfrățită și cu câte în conflict?

Cerința

Ajutați-l pe RAU-Gigel să afle răspunsul la cele două tipuri de întrebări ale sale!

Date de intrare

Fișierul de intrare conflicte.in conține pe prima linie tipul $T$ al întrebării, cu valorile $1$ sau $2$. Dacă $T = 2$, pe următorul rând se află un număr natural nenul reprezentând numărul $Q$ de țări preferate, apoi, separate printr-un spațiu, țările respective. Pe rândurile următoare sunt numele țărilor de pe hartă, adică numere naturale nenule distincte două câte două, dispuse câte unul pe rând, sau mai multe pe rând și separate prin câte un spațiu, în total $N$ numere.

Date de ieșire

Dacă întrebarea e de tipul $1$, fișierul de ieșire conflicte.out va conține un sigur rând pe care se află un singur număr reprezentând răspunsul la întrebarea de tipul $1$. Dacă întrebarea e de tipul $2$, fișierul de ieșire conflicte.out va conține $Q$ rânduri: pe fiecare rând $i$ se vor afla câte două numere separate printr-un spațiu, reprezentând numărul de țări înfrățite, respectiv în conflict cu țara a $i$-a din fișierul de intrare.

Restricții și precizări

• $1 \leq N \leq 10^5, 1 \leq Q ≤ 1 \ 000, Q \leq N$;
• Teste în valoare de $40$ puncte conțin o întrebare de tipul $1$;
• Teste în valoare de $20$ puncte conțin o întrebare de tipul $2$ și $N \leq 1 \ 000, Q \leq 10$;
• Numele țărilor sunt numere naturale nenule, au între $1$ și $9$ cifre (inclusiv) și nu conțin zerouri nesemnificative (la stânga);
• Țările de pe hartă sunt distincte două câte două; la întrebările de tip $2$, lista țărilor preferate ale lui RAU-Gigel nu conține duplicate și este inclusă în lista țărilor de pe hartă;
• Toate țările care au în compunerea numelui lor același set de cifre formează o alianță.

Exemplul 1

conflicte.in

1
1133 123456789
3131 13
1331 2444
678 42 133

conflicte.out

2

Explicație

Pentru întrebarea de tipul $1$ avem: țările $1133, 3131, 13, 1331$ și $133$ formează o alianță, țările $2444$ și $42$ formează o altă alianță, în timp ce $123456789$ și $678$ sunt neutre din punct de vedere politic.

Exemplul 2

conflicte.in

2
2 13 123456789
1133 123456789
3131 13
1331 2444
678 42 133

conflicte.out

4 3
0 0

Explicație

Pentru întrebarea de tipul $2$ avem: țara $13$ este înfrățită cu $4$ țări: $1133, 3131$ și $1331, 133$. Țara 13 este în conflict cu 3 țări: $2444, 678$ și $42$. Cea de-a doua țară preferată a lui RAU-Gigel, țara $123456789$ nu este înfrățită cu nicio altă țară, dar nici în conflict.