ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / 9-р анги /

Архивлагч гэж текстийн ямар нэгэн хэсгийг өөр богино хэсгээр сольж шахдаг програмыг хэлнэ. Орос хэл дээрх текстийг шахах хялбар архивлагчийг зохио. Ямар нэгэн тэмдэгтүүдийг англи цагаан толгойн үсгээр солих толь бичиг болон шахагдах эх текст өгөгдөнө. Өгөгдсөн толь бичгийг ашиглан эх текстийг архивлахдаа гарч буй текстийн хэмжээ хамгийн бага байх ёстой.

Input

Эхний мөрөнд толь бичиг дэх харгалзааны тоо R ба эх текст дэх мөрийн тоо N өгөгдөнө. (1≤N≤1000).

Дараагийн хос R мөр бүрт толь бичгийн харгалзах солилцоонууд өгөгдөнө. Хос мөр бүрийн эхний мөрөнд солилдох тэмдэгтүүд, хоёр дахь мөрөнд англи цагаан толгойн жижиг, том үсгийн аль нэг байна. ( англи жижиг, том үсгүүд нь ялгаатай ). Дараагийн N мөрөнд эх текст байрлана.

Output

Архивлагдсан текст.

Тайлбар : Мөр шилжүүлэх тэмдгийг сольж болохгүй. (өөрөөр хэлбэл зөвхөн мөр доторхийг л солино.)

Мөр бүрийн урт нь 255 тэмдэгтээс ихгүй.

Example

Input:

8 10
рхиватор
b
замен
D
ены
F
зам
G
быт
h
про
d
сжат
f
ом называется
g
Архиватором называется программа, предназначенная для сжатия данных за счет удаления
избыточной информации. В этой задаче вашей целью является разработка простейшего
архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы
символов не встречаются, поэтому они могут быть использованы для замены часто
повторяющихся последовательностей символов.

Заданы последовательности, которые могут быть заменены некоторыми символами английского
алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти
последовательности могут накладываться друг на друга, результат сжатия существенно зависит
от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины.

Output :

Аbg dграмма, предназначенная для fия данных за счет удаления
изhочной информации. В этой задаче вашей целью является разработка dстейшего
аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы
символов не встречаются, поэтому они могут hь использованы для Dы часто
повторяющихся последовательностей символов.

Заданы последовательности, которые могут hь DF некоторыми символами английского
алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти
последовательности могут накладываться друг на друга, результат fия существенно зависит
от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.