In our days of modern technologies it is not common to use text
communication protocols, all computer programs communicate with each other
only via binary protocols when any data are represented as a sequence
of bytes.
So in the company “Perimeter” it was decided that all programs should use
a binary protocol. Programmer Vasya was working hard for a week and, when
finished, proudly went on vacation to restore his nerves. However, Friday
night Baba Zina was wiping the floor at Vasya’s workplace and accidentally
dropped a computer on the floor, after that it stopped working. The
company’s management was in a panic, because there was neither the
programmer nor the program. You have been asked urgently to save the
situation by implementing the missing part, especially the deserialization
of the binary protocol (converting the encoded data into a meaningful
format).
Remember, that during the process of serialization the structured data are
transformed into the set of bytes (numbers from 0 to 255), that is most
convenient to write as a sequence of hexadecimal numbers, consisting of
two digits. Then the sequence is transmitted via a network to another
program that deserializes it, receiving the output of the original data
set.
The transmitted data is the sequence of structures. Each structure has a
name and consists of the ordered set of fields. Each field may be a
non-negative integer, a string or some other structure. During
serialization, the fields are processed sequentially in order of
description, and one after another fall into the final byte stream.
Integers are serialized in 4 bytes, which can be represented as a
hexadecimal number of 8 characters. The sign bit is missing, the order of
bits is from higher to lower. For example,
A string is serialized as an integer, the length of the string, and then
the character codes in the ASCII table (each is one byte). It is known
that all strings include only small Latin letters. For example,
Structures are described by name and enumeration of field types. Each
field type is either “number” or “string” or type of the other
previously described structure. During the serialization of structure,
firstly its first field in the order of description is serialized, then
the second one and so on until its field list does not end.
Input
The first line contains integers n and l that are the number of known
structures and the number of lines with their description (1 ≤ n ≤
240; 2n ≤ l ≤ 103).
The following l lines contain the description of structures.
It is guaranteed that the names of the structures are different and no
name equals “int”, “string” and “struct”.
The first line in the description of the structure consists of the keyword
“struct” and its name\,—\,nonempty string of small Latin letters no
longer than 10 characters. The following lines contain an ordered list of
field types. A type can be either the word “int” or “string” or the
name of the structure that has been already described above. All types are
separated from the beginning of the line with a space. It is guaranteed
that each structure contains at least one field.
The last line contains a byte array, in which was serialized a particular
instance of a structure (or several structures), that is a sequence of
hexadecimal numbers of even length (the digits from 10 to 15 match the
capital letters A-F). It is guaranteed that the sequence is correct and
its length does not exceed 104.
The byte array can be a serialization of several structures. Before
serialization of each structure, the number of this structure in the order
of description in the initial data is serialized (structures are
enumerated from 1 to n).
Output
Output the deserialized instance of structures separated by a line break
in the order in which they appear in the serialized data, in the following
format:
- the first line should be the name of the deserialized structure;
- all following lines in the representation of this instance should
contain a non-zero amount of spaces at the beginning;
- if you remove one space from the beginning of these lines, you will
get a list of field values separated by a line break;
- the number of field values should be equal to the number of types in
the description of the structure;
- if the type of description with the corresponding index is integer,
then output “int” (without the quotation marks) and its value (without
leading zeros) separated by a space.
- if the type of description with the corresponding index is string,
output “string” (without the quotation marks) and a string of small
Latin letters, separated by a space.
- if the type of description with the corresponding index is a
structure, then output a set of strings with the deserialized value of the
structure in this format;
- if you serialize an instance into a sequence of bytes according to
the algorithm described above, it will be byte-by-byte identical to the
corresponding sequence of input data.
It is guaranteed that the output size does not exceed 30 kilobytes.
Sample
input | output |
---|
2 5
struct a
·string
struct b
·a
·int
000000020000000361626300000004000000010000000568656C6C6F
| b
·a
··string abc
·int 4
a
·string hello |
Notes
For clarity, in the example, the leading spaces are replaced by dots. In
all the tests, including the example, there is the format described above
(i.e. spaces instead of dots).
Problem Author: Mikhail Vyatskov
Problem Source: Ural FU Junior Championship 2016