eolymp
bolt
Try our new interface for solving problems
Problems

PreQueL

PreQueL

Time limit 2 seconds
Memory limit 256 MiB

В некоторых упрощенных СУБД называемых PreQueL, единственный допустимый тип названия - CHAR(1) (один символ), а кроме того, его название должно состоять только из английских заглавных букв (от А до Z). Таблица может содержать до 9 столбцов, пронумерованных от 1 до 9. Таблицы называются строчными английскими буквами (от a до z).

Единственно возможный запрос к базе данных сначала соединяет все таблицы (см. пояснение к задаче в конце условия); потом выбирает некоторые строки в соответствии с условиями. Бывают условия двух видов: <column> = <value> или <column1> = <column2>, например, a2 = A или b1 = с4. Все условия должны выполняться одновременно, как если бы они были соединены с помощью оператора AND.

Вы должны написать обработчик запросов к PreQueL, который, с учетом данных ему таблиц и набора условий, будет выдавать результат запроса, то есть те строки которые удовлетворяют всем условиям. Строки в ответе должны быть упорядочены лексикографически по алфавиту.

Input data

Первая строка содержит два целых числа - количество таблиц t (1t26) и количество условий d (1 d 50).

Начиная со второй строки даются t таблиц. В первой строке описания таблицы даются размеры таблицы - r_n и c_n (1c_i9, 1 r_i1000). Далее идёт r_n строк, состоящих ровно из c_n символов каждая. После таблицы идут d строк с условиями.

Output data

Вывести строки результата, каждую строку таблицы выведите в отдельной строке. Гарантируется, что ни один входной запрос не выдаст более 1000 строк.

Examples

Input example #1
2 2
3 2
AX
BX
BY
2 3
ACD
BCC
a1=b1
a2=X
Output example #1
AXACD
BXBCC

Note

  • Строки в выведенном файле должы быть упорядочены по возрастанию.

  • Если мы соединяем таблицы A и B без применения каких-либо условий, число строк в результате будет |A|·|B|.

  • Пусть у нас есть три таблицы (каждая таблица представлена в виде списка строк): {A, B}, {C, D}, {XX, YY, ZZ}. Их соединением будет таблица из 12 строк {ACXX, ACYY, ACZZ, ADXX, ADYY, ADZZ, BCXX, BCYY, BCZZ, BDXX, BDYY, BDZZ}.

Source 2012 Kharkiv, Winter School, Day of Sergey Kopelovich, Problem G