Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:

• se iau tabelul de litere şi dicţionarul de cuvinte permise
• se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt \(c_1c_2…c_k\) care există în dicţionar există şi în tabel dacă fiecare literă \(c_i\) apare în tabel şi pentru i>1, \(c_i\) este vecină în tabel cu litera \(c_{i-1}\).
• din lista sortata de T perechi (\(cuvânt_i\), \(a_i\)), unde \(cuvânt_i\) este un cuvânt iar \(a_i\) este numărul de apariţii în tabel, reconstituie litera \(p_i\) a parolei astfel: \(p_i =\) ‘a’ + ( \(a_i\) mod 26). Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării '?'. Un semn '?' poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.

Cerința

Dat fiind un tabel de litere de dimensiuni N x M, şi o listă a cuvintelor din dicţionar, să se afişeze lista sortată de T perechi de forma 'ci: ai' şi parola Petrei.

Date de intrare

Fişierul cuvinteascunse.in va conţine N + C + 1 linii. Pe prima linie N, M, C – dimensiunile tabelului, şi numărul de cuvinte din dicţionar. Apoi cele N linii ale tabelului:

t1,1 ...t1,m
t2,1 ...t2,m
. . .
tn,1 ...tn,m

urmate de cele C cuvinte din dicţionar, fiecare pe o linie:
cuvânt1
cuvânt2
. . .
cuvântC

Date de ieșire

Fişierul cuvinteascunse.out va conţine pe prima linie T, numărul de cuvinte distincte găsite în tabel. Pe următoarele T linii se vor afla perechi cuvânti ai separate printr-un spaţiu. Pe ultima linie se va afla un şir de caractere reprezentand parola Petrei.

Restricții și precizări

O secvenţă de litere reprezintă un cuvânt dacă se află în dicţionarul dat ca date de intrare. Dicţionarul conţine cuvinte formate din litere aparţinând mulţimii {‘a’...’z’}U{‘A’...’Z’}. Literele mici şi cele mari se consideră egale. Două litere sunt vecine în tabel, dacă celulele lor au o latura sau un colţ comun. Aceeaşi litera din tabel se poate folosi de mai multe ori într-un cuvânt. Dacă acelaşi semn '?' este folosit de mai multe ori într-un cuvânt, trebuie să reprezinte aceeaşi literă de fiecare dată.

• 0 < N < 6
• 0 < M < 6
• 0 < C < 20000

Exemplu:

cuvinteascunse.in

2 2 3
e a
l ?
ea
elena
arc

cuvinteascunse.out

2
ea 3
elena 1
db

Explicație

Am gasit cuvântul “ea” de 3 ori: o data pe prima linie a tabelului, o data pe diagonala principală, inlocuind '?' cu 'a', şi o data ca “?a" inlocuind '?' cu 'e'. Am gasit cuvântul “elena” o data, inlocuind '?' cu 'n'.