Arheologii Orientului Mijlociu doresc să conserve şi restaureze manuscrisele descoperite într-un templu din Mesopotamia. Textele sunt scrise pe tăbliţe de lut în sumeriană, câte un fragment pe fiecare tăbliţă. Alfabetul sumerian foloseşte 26 de litere a căror precedenţă a literelor este cunoscută de cercetători.
Pentru o arhivare corespunzătoare a tăbliţelor, arheologii au ordonat fragmentele prin alipire astfel încât să obţină cel mai mare cuvânt în ordinea lexicografică dată de alfabet.
Dar, în drumul spre muzeu, transportatorul a amestecat tăbliţele.
Cerinţă
Scrieţi un program care cunoscând alfabetul sumerian, numărul n de fragmente şi fragmentele aflate pe tăbliţele amestecate, determină ordinea de arhivare a tăbliţelor.
Date de intrare
Fişierul de intrare antic.in conţine pe prima linie alfabetul sumerian, pe următoarea linie numărul n, iar pe următoarele n linii fragmentele aflate pe tăbliţe, pe fiecare linie aflându-se un singur fragment.
Date de ieşire
Fişierul de ieşire antic.out va conţine o singură linie pe care va fi scrisă ordinea stabilită de arheologi.
Restricţii
- 1 ≤ n ≤ 1000
- 1 ≤ lungimea unui fragment ≤ 100
- Ipotetic, vom presupune că alfabetul sumerian va conţine 26 de litere mici ale alfabetului englezesc, dar a căror precedenţă este modificată.
- Dacă sunt mai multe soluţii se va alege ultima lexicografic din punct de vedere a indicilor.
- Tăbliţele nu pot fi „sparte”.
Exemple
| antic.in |
antic.out |
Explicaţie |
qwertyuiopasdfghjklzxcvbnm
4
qux
am
pas
wrtef
|
2 3
4 1
|
Precedenţă literelor din alfabet ‘q’<’w’<’e’<…<’m’
Prin alipire se pot obţine 24 de rearanjări posibile, dar cea mai mare din punct de vedere lexicografic este aranjarea:
2 3 4 1
Fragmentul ”qux” este mai mic lexicografic decât fragmentul “pas”, iar ”am”>”wrtef”
|