Oracolul decide!
La un concurs participa N concurenti. Fiecare concurent primeste o foaie de hârtie pe care va scrie un cuvânt având cel mult 100 de caractere (litere mici ale alfabetului englez). Cuvintele vor fi distincte.
Pentru departajare, concurentii apeleaza la un oracol. Acesta produce si el un cuvânt. Va câstiga concurentul care a scris cuvântul "cel mai apropiat" de al oracolului.
Gradul de "apropiere" dintre doua cuvinte este lungimea subcuvântului comun de lungime maxima. Prin subcuvânt al unui cuvânt dat se întelege un cuvânt care se poate obtine din cuvântul dat, eliminând 0 sau mai multe litere si pastrând ordinea literelor ramase.
Se cunosc cuvântul c0 produs de oracol si cuvintele ci, i = 1, …, N scrise de concurenti. Pentru a ajuta comisia sa desemneze câstigatorul, se cere ca pentru fiecare i sa identificati pozitiile literelor ce trebuie sterse din c0 si din ci astfel încât prin stergere sa se obtina unul dintre subcuvintele comune de lungime maxima.Fisier de intrare: ORACOL.IN
Linia 1: N
· numar natural nenul, reprezentând numarul concurentilor;
Linia 2: c0
· cuvântul produs de oracol;
Liniile 3..N+2: cuvant
· pe aceste N linii se afla cuvintele scrise de cei N concurenti, un cuvânt pe o linie;
Date de iesire
Fisier de iesire: ORACOL.OUT
Liniile 1..2*N: pozitiile literelor ce trebuie sterse
· pe fiecare linie i (i = 1, 3, ..., 2*N – 1) se vor scrie numere naturale nenule, separate prin câte un spatiu, reprezentând pozitiile de pe care se vor sterge litere din cuvântul produs de oracol; pe fiecare linie j (j = 2, 4, ..., 2*N) se vor scrie numere naturale nenule, separate prin câte un spatiu, reprezentând pozitiile de pe care se vor sterge litere din cuvântul concurentului cu numarul j/2.
Restrictii
·
2
<= N <= 100
·
Daca exista mai multe solutii,
în fisier se va scrie una singura.
·
Daca dintr-un cuvânt nu se va
taia nici o litera, linia respectiva din fisierul de intrare va ramâne vida.