HTML 문서는 계층 구조를 가지고 있다. 이는 이름을 갖는 각 원소가 다른 원소들을 포함할 수 있다는 것을 의미한다. div 명령어만 들어있는 HTML 문서를 생각해보자. 이런 문서는 아래와 같은 형태로 구성되어 있다.

<div id='name' class='class1 class2 ... classK'> // 원소의 시작
... // 원소의 내용
</div> // 원소의 끝

즉, 각각의 단일 원소는 시작 줄과 끝줄이 있고, 그 두 줄 사이에 빈 줄이 있거나 다른 원소들이 있을 수 있으며, 문서는 이런 원소들을 여러 개 포함하고 있다.

각 원소들의 이름은 알파벳 소문자로 이루어진 문자열이며, 서로 다르다. 이름이 E인 원소(원소 E)가 이름이 F인 원소(원소 F) 안에 들어있을 경우, ‘E가 F 안에 포함되어 있다’ 혹은 ‘F가 E를 포함한다’고 하자. 또, E가 F 안에 포함되어 있으면서, E를 포함하면서 F 안에 포함되어 있는 다른 원소 G가 존재하지 않는 경우, ‘F는 E의 부모 원소’라고 하자.

CSS는 스타일시트 언어로써 웹브라우저에서 HTML 문서의 구성 방식을 표현할 때 쓰인다. 이 언어의 주요 기능으로는 선택자(selector)와 분류자(classifier)가 있다.

분류자는 점을 이용해서 한 개 이상의 클래스를 나타내는데, 클래스는 알파벳 소문자로 이루어진 문자열이다. 예를 들어 ".banana.apple", ".banana", ".apple.banana.mango" 등이 모두 분류자이다. 각 분류자는 각각 2, 1, 3개의 클래스를 포함하고 있다. HTML 문서의 한 원소가 분류자를 포함한다는 것은 분류자에 속한 클래스들이 전부 그 원소에 나열되어 있다는 것을 의미한다.

선택자는 한 개 이상의 분류자들과 '>' 연산으로 이루어져 있다.

• 만약 S가 정확히 한 개의 분류자 k로 이루어져 있다면, HTML 원소가 S를 포함하기 위해서는 그 원소가 k를 포함해야 한다.
• 만약 S가 'T k' (T는 선택자, k는 분류자) 형태로 이루어져 있다면, HTML 원소 E가 S를 포함하기 위해서는 E가 k를 포함하고 E를 포함하는 원소 F가 존재해서 F가 T를 포함해야 한다.
• 만약 S가 'T > k' (T는 선택자, k는 분류자) 형태로 이루어져 있다면, HTML 원소 E가 S를 포함하기 위해서는 E가 k를 포함하고 E의 부모 원소 F가 T를 포함해야 한다.

입력 형식

• 첫 번째 줄에는 HTML 문서의 줄의 수 N이 주어진다. (2 ≤ N ≤ 10,000, N은 짝수)
• 두 번째 줄부터 N개의 줄에는 HTML 문서가 주어진다. 각 줄은 문제에서 언급한 ‘원소의 시작’ 또는 ‘원소의 끝’이여야 한다.
• N+2번째 줄에는 선택자의 수 M이 주어진다. (1 ≤ M ≤ 5) 그 다음 줄부터 M개의 줄에는 선택자가 주어진다.

출력 형식

< div id=’name’ class=’class1 class2 . . . classK’> element beginning
... element content
</div> 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. 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.

• 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 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.

입력

• 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.

출력

SCORING

입출력 예

input

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

output

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

출처:coci/2013-2014/contest7
번역:functionx