Петре е препишувач. Тоа е лоша карактеристика и лоша навика. Неговата другарка Рита сака да го одвикне од препишувањето. Точниот одговор на едно прашање од домашната задача се состои од еден збор. Зборот е напишан со мали латинични букви. Рита знаела дека Петре ќе се обиде да го препише одговорот и таа одговорот го запишала нечитко. Петре го препишал, а на местата каде што не знаел која буква е запишана (не можел да ја препознае) ставил „#“.
Сега Петре ја моли Рита да му ги каже буквите кои треба да се стават на местата со „#“. Таа, за да му докаже дека е потешко да се препишува отколку да се научи, му дава по K различни кандидат - букви за секоја позиција со #. Откако Петре ги запишал сите можни зборови кои може да се состават со сите кандидат - букви дадени од Рита, таа му дала уште една информација: „ Ако се подредат сите овие зборови по азбучен (абецеден) редослед, тогаш бараниот одговор е X-тиот по ред збор“.

Очигледно Рита се потрудила да го намачи. Дали вие може да утврдите за кој збор се работи? Напишете програма која го решава овој проблем.

Влез

Во првиот ред се запишани целите броеви N, M, K и X (1 ≤ N ≤ 500, 1 ≤ M ≤ N, 1 ≤ K ≤ 26, 1 ≤ X ≤ 1 000 000 000).
Во вториот ред е запишан зборот со должина N кој Петре го запишал во тетратката, составен од мали букви од англиската абецеда и знакот „#“.
Секој од следните M редови содржи по еден збор со должина K. i-тиот ваков збор ги содржи кандидат - буквите кои може да ја заменат i-тата „#“. Нема да има две исти кандидат-букви во ист ред.
Бројот X секогаш ќе биде помал или еднаков на вкупниот број на зборови што може да се формираат.

Бодување:
За 20% од поените ќе важи: M = 1 и K = 3.
За дополнителни 30% од поените ќе важи: M = 1.

Излез

Во единствениот ред од излезот запишете го бараниот збор, т.е. X-тиот по ред збор по азбучен редослед.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
10 2 3 2
mad#gas#ar
ask
akt

излез
madagaskar

влез
4 1 2 2
#rak
bm

излез
mrak

Објаснување за првиот пример: Сите можни зборови подредени по азбучен редослед се: „madagasaar”, „madagaskar”,„madagastar”, „madkgasaar”,„madkgaskar”, „madkgastar”, „madsgasaar”,„madsgaskar”, „madsgastar”