"T9" ir sistēma, kas izstrādāta strauji augošajām mobilo tālruņu īsziņu sūtīšanu vajadzībām. Tā balstās uz mobilā tālruņa atmiņā esošo vārdnīcu. Tagad pietiek katram burtam atbilstošo cipara taustiņu nospiest vienu reizi un pirmais vārds, kas atbilst nospiestajai taustiņu kombinācijai, tiks parādīts uz tālruņa ekrāna.

Burtu izvietojums uz mobilā tālruņa ciparu taustiņiem ir sekojošs:

Katrs ziņojums sastāv no vārdu virknes, kur katrus divus blakus vārdus atdala tukšumsimbols.

Uzrakstiet programmu, kas simulē "T9" darbu!

Ievaddatu pirmajā rindā dota naturāla skaitļa M(vārdu skaits vārdnīcā, 1 ≤M≤100) vērtība.

Katrā no nākošajām M faila rindām dots pa vienam vārdnīcas vārdam katrā. Vārdi ir sakārtoti augošā secībā un satur tikai angļu alfabēta lielos burtus (A-Z). Neviena vārda garums nepārsniedz 100 simbolus.

Nākošajā faila rindā dots naturāls skaitlis N(taustiņu nospiedienu skaits uz mobilā telefona klaviatūras, 1≤N≤100).

Nākošajā faila rindā doti N nenules cipari, kas atdalīti ar tukšumsimboliem. Šī ciparu virkne apraksta nospiesto ciparu taustiņu virkni.

Izvaddatu vienīgajā rindā jāizvada iegūtā ziņojuma teksts. Katrs burts katrā vārdā, kas nav atrodams vārdnīcā, jāaizstāj ar zvaigznīti ('*'). Ja dotai ciparu virknei vārdnīcā atbilst vairāk par vienu vārdu, tad jāizvada vārds, kas vārdnīcā atrodas tuvāk sākumam.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā