Érintőképernyős billentyűzet

Manapság az emberek már nem használnak hardveres billentyűzetet, csak érintőképernyőket. Általában rossz betűt érintenek meg a vaskos ujjaikkal, mert a képernyőterület értékes, és ezért a betűk túl kicsik.

Egy-egy szó begépelése után rendszerint lefut egy helyesírás-ellenőrző, és felajánl más szavakat, amelyekből kiválaszthatjuk a helyes írásmódot. A feladatod, hogy rendezd ezt a listát úgy, hogy a legvalószínűbb szavak kerüljenek felülre.

Egy tipikus érintőképernyős billentyűzet a következőképpen néz ki:

qwertyuiop
asdfghjkl
zxcvbnm

Egy szó begépelésénél a betűk közötti távolságot kell használni, amely a begépelt és a felkínált betű közötti vízszintes és függőleges távolságok összege. Ha például a begépelt betű egy w, annak a távolsága az e-től 1, míg a z-től 3.

A begépelt szó és a helyesírás-ellenőrző listáján szereplő szavak mind azonos hosszúságúak. Két szó közötti távolság alatt a megfelelő betűik közötti távolságok összegét értjük. Az ifpv és az icpc szavak távolsága például 3.

A bemenet specifikációja

A bemenet első sora t-t, a tesztesetek számát adja meg (0 < t < 20). Minden teszteset egy olyan sorral kezdődik, amely egy sztringet és egy l egész számot tartalmaz. A sztring az érintőképernyős billentyűzeten begépelt szó, míg l a helyesírás-ellenőrző listáján szereplő elemek száma (0 < l ≤ 10). Ezt l sor követi, amelyek mindegyike a lista egy-egy szavát tartalmazza. Feltételezheted, hogy egy teszteseten belül minden szó azonos hosszúságú, és egyik sem hosszabb 10 000 karakternél (amelyek mind angol kisbetűk 'a'-tól 'z'-ig). Továbbá egy teszteseten belül minden szó pontosan egyszer fordul elő a helyesírás-ellenőrző listáján.

A kimenet specifikációja

Minden tesztesetre a listán szereplő szavakat kell a kimenetre írni, a begépelt szótól mért távolságuk alapján növekvő sorrendbe rendezve. Ha két szónak azonos a távolsága a begépelt szótól, akkor azokat betűrendben kell kiírni. A szavak mellé (egy szóközt követően) írd ki a begépelt szótól mért távolságukat is!

Példa bemenet

1. 2
2. ifpv 3
3. iopc
4. icpc
5. gcpc
6. edc 5
7. wsx
8. edc
9. rfv
10. plm
11. qed

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. icpc 3
2. gcpc 7
3. iopc 7
4. edc 0
5. rfv 3
6. wsx 3
7. qed 4
8. plm 17

letöltés szöveges állományként