CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 5 s
Memory limit: 256 MB
Page \(1/3\)
Popular HTML documents have a hierarchical structure. This means they consist of \(so-ca\)lled elements
that have a name and certain attributes and can contain other elements. In this task we consider documents
that consist only of nested div elements. Specifically, each document consists of lines of the following form:

element end
Thus, a single element consists of a line that detones its beginning, a line that denotes its end, and in
between these two lines is the content of the element which can either be empty of consist of a series
of other elements that can again contain other elements and so on. The document itself consists of a
series of elements (some of which may contain other elements). Additionally, the following holds for a
representation of an element:
• The name of the element is an array of lowercase letters of the English alphabet. The name uniquely
identifies the element in the document, and no two different elements have the same name.
• Each of the classes of elements is also an array of lowercase letters of the English alphabet. If a class
is listed in the initial list of elements, we say that an element belongs \(to\) that class. Each element
can belong to one or more different classes. Different elements can belong to same classes.
• The only space charactes that appear in the representation of an element are, respectively, one
single space before id, one single space before class and possible spaces between individual classes,
exactly one space between two adjacent classes.
If element \(E\) is written in the content of element \(F\) (anywhere between the lines that denote the beginning
and the end of element \(E\)), we say that \(F\) contains \(E\) or, in other words, that \(E\) \(is\) contained in \(F\). We
say that element \(E\) is the parent of element \(F\) if \(F\) is contained in \(E\) and there is not a single element \(G\)
such that \(F\) is contained in \(G\) and \(G\) is contained in \(E\).
CSS is a style sheet language used for describing the look and formatting of HTML elements when seen
in a Web browser. An important part of that language are \(so-ca\)lled selectors and classifiers. A classifier
is a series of characters that begins with a dot and is followed by one or more classes separated by dots.
Again, only lowercase letters of the English alphabet must appear in classes. Some examples of classifiers
are: ".banana.apple", ".banana", ".apple.banana.mango". These classifiers consist of two, one and three
classes, respectively. We say that a certain HTML element corresponds to a classifier if it belongs to all
classes that are listed in the classifier.
A selector consists of one or more classifiers and two adjacent classifiers in a selector can be separated
with either a single space or a series of spa\(ce-gr\)eater th\(an-sp\)ace characters (‘ > ’). Correspondence of
an HTML element to a selector is recursively defined in the following way:
• If \(S\) is a selector which consists of exactly one classifier \(k\), the element corresponds to \(S\) if it corres-
ponds to \(k\).
• If \(S\) is a selector in the form of ‘\(T\) \(k\)’ where \(T\) is a selector and \(k\) is a classifier, the element \(E\)
corresponds to \(S\) if it corresponds to \(k\) and is contained (not necessarily directly) in an element \(F\)
which corresponds to \(T\).
• If \(S\) is a selector in the form of ‘\(T > k\)’ where \(T\) is a selector and \(k\) is a classifier, the element \(E\)
corresponds to \(S\) if it corresponds to \(k\) and its parent \(F\) corresponds to \(T\).
CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 5 s
Memory limit: 256 MB
Page \(2/3\)
You are given a document which consists of \(N\) lines and you are given \(M\) selectors. Write a programme that
will, for each given selector, output the names of all elements that correspond to it. For each individual
selector, the names must be output in the order they appear in the given document.

In test cases worth 50% of total points, it will hold that selectors will not contain the character ‘>’.
CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 5 s
Memory limit: 256 MB
Page \(3/3\)

The first line of input contains an even integer \(N\) (2 ⩽\(N\) ⩽10 000), the number of lines in the document.
The following \(N\) lines contain the lines of the document. Each line will correspond to a beginning or an
end of an element as described in the task.
The following line contains the integer \(M\) (1 ⩽\(M\) ⩽5), the number of selectors.
Each of following \(M\) lines contains a single selector.
The names of all elements and classes in the input data will consist of only lowercase letters of the English
alphabet and their length will not be greater than 20 characters.
Additionally, not a single line in the input data will be longer than 5 000 characters and the sum of the
lengths of all the lines in the input will not exceed 5 000 000.

For each selector in the input data, output a single line. Firstly, output the number of elements that
correspond to the given selector and then the names of corresponding elements in aforementioned order.

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Olympiad