CSS Selector Matching

Modern HTML documents are hierarchical. A document is made of elements, each with a name, attributes, and optional nested elements. Assume only div elements appear.

An element starts with a line of the form:

<div id='name' class='class1 class2 ... classK'>

Its content may be empty or contain zero or more nested elements, then ends with:

</div>

Rules:

• The element id uses lowercase English letters and is unique in the document.
• class names also use lowercase letters. One element may belong to many classes, and different elements may share classes.
• On the opening line, spaces appear only before id, before class, and between adjacent class names.

If element E appears anywhere between F's opening and closing lines, F contains E.

If F contains E and no other element G both contains F and is contained in E, then E is the parent of F.

CSS describes how elements are displayed. This problem uses classifiers and selectors only.

A classifier starts with . and lists dot-separated class names, for example .banana.apple. An element matches a classifier when it has every listed class.

A selector is one or more classifiers separated by spaces, >, or space strings. Matching is defined recursively:

• A selector that is a single classifier k matches every element with those classes.
• For T k, element E matches when E matches k and is contained in some element that matches T (not necessarily a direct child).
• For T > k, element E matches when E matches k and its parent matches T.

Given an N-line document and M selectors, print the ids of all matching elements for each selector in document order.

The first line contains an even integer N (2 ≤ N ≤ 10 000), the number of document lines.

The next N lines are the document. Each line is either an opening or closing tag.

The following line contains M (1 ≤ M ≤ 5), the number of selectors.

The next M lines contain the selectors.

Every id and class uses only lowercase English letters and has length at most 20.

Each input line has length at most 5 000, and the sum of all line lengths is at most 5 000 000.

For each selector, print one line: the match count, then the matching ids in document order separated by spaces. If there are no matches, print 0 only.