НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ

Департамент Информатика

XVIIІ РЕПУБЛИКАНСКА СТУДЕНТСКА ОЛИМПИАДА ПО ПРОГРАМИРАНЕ

13 - 14 май 2006 г.

Задача B. T9

Т9 е система, разработена да задоволява растящите нужди за бързо изпращане на текстови съобщения (SMS). Системата е базирана на речник в паметтна на мобилен телефон. По време на писането е най-добре за всяка буква да се прави само по едно натискане на клавиш (въпреки, че клавишите не стигат...). Извежда се първата дума от речника, която започва с букви, съответстващи на натиснатите клавиши. Подредбата на буквите на клавишите на телефона е показана на таблицата:

1	2	3	4	5	6	7	8	9
интервал	A B C	D E F	G H I	J K L	M N O	P Q R S	T U V	W X Y Z

Всяко съобщение се състои от поредица думи, разделени с по един интервал. Напишете програма B, която да симулира системата Т9, базирана на даден речник.

Вход. На първия ред на стандартния вход се въвежда цяло число K – броят на тестовите примери. Всеки тестов пример има следната структура:

Първият ред се състои от естествено число М, 1 ≤ M ≤ 100, съответстващо на броя на думите в речника. Следващите М реда съдържат самите думи, по една на ред, подредени лексикографски. Думите се състоят от не повече от 100 главни латински букви (A-Z). На следващия ред е записано естественото число N, 1 ≤ N ≤ 100, броят на кликванията по малката и неудобна клавиатурка. На следващия ред има N естествени числа от 1 до 9, разделени с по интервалче. Всяко число съответства на натиснат бутон в реда на писането.

Изход. За всеки тестов пример се извежда на стандартния изход единствен ред, който по принцип би трябвало да съдържа съобщението, получено от Т9. Всяка буква от дума, която не е от речника трябва да бъде заменена със звездичка (*). Ако може да се изведе повече от една дума, то се извежда първата в лексикографска наредба.