Gimigpt

În urma rezultatelor bune obținute, Gimi a devenit foarte popular printre colegii lui. Însă, nu în modul pe care și-l dorea. Acum, majoritatea colegilor au început să-i pună diverse întrebări teoretice.

Gimi a primit o listă de $N$ întrebări de la colegii săi, și îsi propune să răspundă în ordine la ele. A $i$-a întrebare $q_i$ constă dintr-un șir de caractere alcătuit numai din litere mici ale alfabetului englez. Ce a observat însa este că el poate primi aceeași întrebare, formulată diferit – așa că, dacă întrebarea $q_i$ se aseamănă cu cel puțin o întrebare $q_j \ ($ cu $1 \leq j < i)$ la care deja a răspuns, atunci el nu va mai răspunde la întrebarea $q_i$.

Gimi și-a definit următoarele criterii de asemănare între întrebarea $q_j$ și întrebarea $q_i$:

• Egalitate $(E)$: Dacă întrebarea $q_i$ este egală cu întrebarea $q_j$ , atunci $q_i$ și $q_j$ se aseamănă prin criteriul $E$.
• Inserare $(I)$; Dacă prin inserarea unui singur caracter în $q_i$, aceasta devine egală cu $q_j$ , atunci $q_i$ și $q_j$ se aseamănă prin criteriul $I$.
• Ștergere $(S)$: Dacă prin ștergerea unui singur caracter din $q_i$, aceasta devine egală cu $q_j$ , atunci $q_i$ și $q_j$ se aseamănă prin criteriul $S$.
• Modificare $(M)$: Dacă prin modificarea unui singur caracter din $q_i$, aceasta devine egală cu $q_j$ , atunci $q_i$ și $q_j$ se aseamănă prin criteriul $M$.

Notăm cu $T$ mulțimea de criterii de asemănare pe care el le utilizează. De exemplu, dacă $T = EI$, el va folosi numai criteriile $E$ și $I$ pentru a determina dacă întrebările seamănă sau nu. Dacă $T = EISM$, atunci el va folosi toate cele $4$ criterii.

Gimi pornește cu prima întrebare din listă și va răspunde la ea. După aceea, începând de la a doua întrebare până la ultima, procedează astfel:

• Dacă întrebarea $q_i$ seamănă cu cel puțin o întrebare $q_j$ pe baza a cel puțin unuia dintre criteriile din $T$, atunci NU va răspunde la întrebarea $q_i$.
• Altfel, va răspunde la întrebarea $q_i$.

Fiind un set foarte mare de întrebări, Gimi și-ar dori să determine: pentru o mulțime de criterii $T$, la care întrebări va răspunde (și la care nu).

Cerință

Scrieţi un program care, cunoscând $N$ , numărul de întrebări, $T$, criteriile de asemănare folosite, respectiv cele $N$ întrebări $q_1, q_2, …, q_N$ , afișează pentru fiecare dintre aceste întrebări dacă se va răspunde la ea sau nu.

Date de intrare

Fişierul de intrare gimigpt.in conține pe prima linie un număr natural $N$ , reprezentând numărul de întrebări, și un șir de caractere $T$, care conține criteriile de asemănare, separate printr-un spațiu.
Următoarele $N$ linii conțin, în ordine, cele $N$ întrebări, câte o întrebare pe o linie.

Date de ieșire

Fişierul de ieşire gimigpt.out va conţine $N$ linii. Linia $i$ va conține valoarea $1$ dacă se va răspunde la cea de a $i$-a întrebare din fișierul de intrare, respectiv valoarea $0$ în caz contrar.

Restricții și precizări

• $T \in \{E$, $EI$, $ES$ , $EM$, $EIS$, $EIM$, $ESM$, $EISM \}$
• $1 \leq N \leq 80 \ 000$
• $2 \leq LEN(q_i) \leq 26$, pentru oricare $1 \leq i \leq N$ , unde LEN reprezintă lungimea șirului.
• Testele sunt grupate. În cadrul fiecărui subtask, sunt precizate și grupele de teste asociate

Exemplul 1

gimigpt.in

5 EISM
abc
abb
abbx
abc
bbb

gimigpt.out

1
0
1
0
1

Explicație

Se va răspunde la prima întrebare $abc$ A doua întrebare $abb$ se aseamănă cu întrebarea $abc$ pe baza criteriului $M$ (se modifica ultima literă din $b$ în $c$), deci nu se va răspunde.
Se va răspunde la a treia întrebare $abbx$. Se observă că, dacă s-ar fi răspuns la întrebarea $abb$, atunci nu s-ar mai fi răspuns la întrebarea curentă.
A patra întrebare $abc$ se aseamănă cu întrebarea $abc$ pe baza criteriului $E$ (șirurile sunt egale), deci nu se va răspunde la ea.
Se va răspunde la întrebarea $bbb$.

Exemplul 2

gimigpt.in

4 EI
abc
abb
ac
abbx

gimigpt.out

1
1
0
1

Explicație

Se va răspunde la prima întrebare $abc$.
Se va răspunde la a doua întrebare $abb$.
Ea nu se aseamănă cu întrebarea $abc$ pe baza criteriilor $E$ și $I$.
Nu se va răspunde la a treia întrebare $ac$. Ea se aseamănă cu întrebarea $abc$ pe baza criteriului $I$ (prin inserarea literei $b$).
Se va răspunde la întrebarea $abbx$. Ea se aseamănă cu întrebarea $abx$ pe baza criteriului $S$ (prin ștergerea literei $x$), care nu face parte din $T$. Criteriul $I$ presupune strict inserarea unei litere în șirul curent $(abbx)$ și nu inserarea unei litere într-o întrebare la care s-a răspuns deja.