teroristi

Inspiraţi de faimoasa grupare Al-Qaeda, teroriştii din oraşul Tomis s-au hotărât să saboteze Olimpiada Naţională de Informatică. Pentru a-şi pune planul în aplicare ei au răpit-o pe Miruna şi au trimis o scrisoare concurenţilor în care cer o răscumpărare foarte mare. Ca măsură de siguranţă, scrisoarea nu a fost scrisă de mână, ci a fost compusă lipind pe o foaie litere decupate dintr-un ziar. Detectivul Mirunel are un plan pentru a determina identitatea teroriştilor. Primul lucru pe care vrea să îl facă Mirunel este să demonstreze că teroriştii citesc Dilema veche. Detectivul are ultimul număr al revistei şi vrea să ştie dacă scrisoarea teroriştilor putea fi scrisă decupând litere doar din această ediţie. Din păcate sarcina este prea grea pentru Mirunel, deoarece atunci când decupează o bucată dintr-un ziar, aceasta va conţine $2$ litere, câte una pe fiecare faţă. Fiecare bucată de ziar poate fi utilizată în două moduri, în funcţie de litera care va fi folosită la reconstituirea scrisorii trimise, iar acest lucru l-a încurcat de tot pe Mirunel.

Cerinţă

Scrieţi un program care să determine o modalitate validă de reconstituire a scrisorii trimise de terorişti, folosind doar bucăţile de ziar decupate de Mirunel.

Date de intrare

Fişierul de intrare teroristi.in conţine pe prima linie două numere naturale $n$ şi $m$, reprezentând lungimea scrisorii trimise de terorişti, respectiv numărul de bucăţi de ziar decupate. Pe a doua linie se află mesajul scrisorii sub forma unui şir de $n$ litere mici aparţinând alfabetului englez. Fiecare din următoarele $m$ linii conţine exact $2$ caractere din alfabetul englez separate prin spaţiu, reprezentând literele înscrise pe cele două feţe ale unei bucăţi de ziar.

Date de ieșire

Fişierul de ieşire teroristi.out va conţine o singură linie pe care se va găsi un şir de $n$ numere distincte din mulţimea $\{1, 2, \dots, m \}$. Pe poziţia $i$ din şirul afişat se va afla indicele bucăţii de ziar (în ordinea în care acestea apar în fişierul de intrare) folosite pentru a reprezenta cea de a $i$-a literă din scrisoare.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$
• $n \leq m \leq 1 \ 000 \ 000$
• Pentru $10\%$ din teste $n, m = 3$
• Pentru alte $10\%$ din teste $n, m \leq 15$
• Pentru alte $30\%$ din teste $n, m \leq 1 \ 000$
• Dacă există mai multe soluţii, poate fi afişată oricare dintre ele.
• Se garantează că pe datele de test există întotdeauna soluţie.

Exemplul 1

teroristi.in

6 8
miruna
b a
m i
f a
u g
f m
a g
b r
n a

teroristi.out

5 2 7 4 8 3

Explicație

Se vor folosi următoarele bucăţi:

$5$ – f m
$2$ – m i
$7$ – b r
$4$ – u g
$8$ – n a
$3$ – f a