ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2106. Deserialization

Time limit: 2.0 second
Memory limit: 64 MB
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,
Problem illustration
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,
Problem illustration
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; 2nl ≤ 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

inputoutput
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