COI '13 #1 CSS

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem types

Popular HTML documents have a hierarchical structure. This means they consist of so-called 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:

<div id='name' class='class1 class2 ... classK'>    element beginning
...                                                element content
</div>                                             element end

Thus, a single element consists of a line that denotes 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 or 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 the same classes.
  • The only space characters 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-called 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 "space", "greater than", and "space" 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 corresponds 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.

You are given a document which consists of N lines and you are given M selectors. Write a program 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.

Input Specification

The first line of input contains an even integer N (2 \le N \le 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 \le M \le 5), the number of selectors.

Each of the 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.

Output Specification

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.

Constraints

SubtaskPointsConstraints
150Selectors will not contain the character >.
250No additional constraints.

Sample Input

Copy
22
<div id='a' class='banana mango'>
<div id='b' class='orange'>
<div id='c' class='banana'>
<div id='d' class='apple mango orange'>
<div id='e' class='orange'>
</div>
</div>
</div>
</div>
<div id='f' class='orange apple'>
<div id='g' class='apple'>
<div id='h' class='orange apple'>
<div id='i' class='banana'>
</div>
</div>
</div>
<div id='j' class='banana'>
</div>
</div>
</div>
<div id='k' class='glupo voce daj mi sarme'>
</div>
5
.banana
.banana > .sarme
.banana > .orange > .banana
.banana .apple.orange > .orange
.mango > .orange .banana

Sample Output

Copy
4 a c i j
0
2 c j
1 e
3 c i j

Comments

There are no comments at the moment.