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

Вот и в компании «Периметр» решили перевести все программы на использование бинарного протокола. Программист Вася неделю корпел и, всё доделав, с гордостью ушёл в отпуск восстанавливать нервы. Но баба Зина вечером в пятницу, протирая пол под рабочим местом Васи, случайно уронила на пол компьютер, после чего тот перестал работать. Руководство компании в панике — ни программиста, ни программы. Вас попросили в срочном порядке спасти положение, реализовав потерянную часть, а именно десериализацию бинарного протокола (преобразование закодированных данных в осмысленный формат).

Напомним, что при обмене информацией структурированные данные в процессе сериализации превращаются в набор байтов (чисел от 0 до 255), которые удобнее всего записать как последовательность шестнадцатеричных чисел, состоящих из двух цифр каждое. Затем эта последовательность передаётся по сети другой программе, которая её десериализует, получая на выходе исходный набор данных.

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

Целые числа сериализуются в 4 байта, которые можно представить в виде шестнадцатеричной записи этого числа из 8 символов. Знаковый бит отсутствует, порядок битов — от старших к младшим. Например,

Строки сериализуются как целое число — длина строки, а затем коды символов в таблице ASCII (по 1 байту). Известно, что в строчках встречаются только маленькие латинские буквы. Например,

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

В первой строке записаны целые числа n и l — количество известных структур и количество строк с описанием структур (1 ≤ n ≤ 240; 2n ≤ l ≤ 10³). В следующих l строках задано описание структур. Гарантируется, что имена структур различны и никакое имя не совпадает с «int», «string» и «struct».

Первая строка в описании структуры: ключевое слово «struct» и название — непустая строка из маленьких латинских букв не длиннее 10 символов. В последующих строках записан упорядоченный список типов полей. Тип может быть либо словом «int», либо словом «string», либо названием структуры, которая уже была описана выше. Все типы отделены от начала строки пробелом. Гарантируется, что каждая структура содержит хотя бы одно поле.

В последней строке задан массив байт, в который был сериализован конкретный экземпляр структуры (или нескольких структур) — последовательность шестнадцатеричных цифр чётной длины (цифрам от 10 до 15 соответствуют заглавные латинские буквы A-F). Гарантируется, что последовательность является корректной и её длина не превосходит 10⁴.

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

Выведите десериализованные экземпляры структур через перевод строки в том порядке, в котором они идут в сериализованных данных, в следующем формате:

Гарантируется, что размер выходных данных не превосходит 30 килобайт.

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