CSS 선택자 매칭

오늘날 많이 쓰이는 HTML 문서는 계층 구조를 가진다. 문서는 요소로 이루어지며, 각 요소는 이름과 여러 속성을 가지고 다른 요소를 포함할 수 있다. 여기서는 div 요소만 등장한다고 가정한다. 각 요소는 아래 형태의 한 줄로 시작을 표시한다.

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

요소의 내용은 비어 있거나, 그 사이에 다른 요소가 0개 이상 올 수 있다. 내용이 끝나면 아래 한 줄로 끝을 표시한다.

</div>

문서는 여러 요소의 집합이며, 일부 요소는 다른 요소를 포함할 수 있다.

• 요소 이름(id)은 영문 소문자 알파벳으로만 이루어지며, 문서 안에서 유일하다.
• class도 영문 소문자 알파벳으로만 이루어진다. 한 요소는 여러 class에 동시에 속할 수 있고, 서로 다른 요소가 같은 class 집합을 가질 수 있다.
• 시작 줄에서 공백은 id 앞 1개, class 앞 1개, 인접한 class 이름 사이에 각각 1개만 허용된다.

요소 E가 요소 F의 시작 줄과 끝 줄 사이 어디에든 있으면 F가 E를 포함한다고 한다.

F가 E에 포함되고, F를 포함하면서 E에도 포함되는 다른 요소 G가 없으면 E는 F의 부모다.

CSS는 HTML 요소의 표시 방식을 기술하는 스타일 시트 언어다. 여기서는 분류자(classifier) 와 선택자(selector) 만 다룬다.

분류자는 점(.)으로 시작하며, 점으로 구분된 class 이름들의 나열이다. 예: .banana.apple, .banana, .apple.banana.mango. 분류자에 나열된 모든 class를 가진 요소가 그 분류자에 속한다.

선택자는 하나 이상의 분류자로 이루어지며, 인접한 분류자는 공백, >, 공백 문자열로 구분된다. 요소가 선택자에 해당하는지는 아래 규칙으로 재귀적으로 정의한다.

• 선택자 S가 분류자 k 하나뿐이면, k에 속하는 모든 요소가 S에 해당한다.
• S가 T k 형태이고 T가 선택자, k가 분류자이면, k에 속하는 요소 E가 T에 해당하는 어떤 요소 F에 포함되면 E도 S에 해당한다. 직접 자식일 필요는 없다.
• S가 T > k 형태이면, k에 속하는 요소 E의 부모 F가 T에 해당할 때 E도 S에 해당한다.

N줄짜리 문서와 M개의 선택자가 주어질 때, 각 선택자에 해당하는 모든 요소의 id를 문서에 나타난 순서대로 출력하는 프로그램을 작성하시오.

첫 줄에 짝수 정수 N(2 ≤ N ≤ 10 000)이 주어지며, 전체 문서 줄 수를 뜻한다.

이어지는 N줄에 문서 내용이 주어진다. 각 줄은 한 요소의 시작이거나 끝이다.

그다음 줄에 선택자 개수 M(1 ≤ M ≤ 5)이 주어진다.

이어지는 M줄에 각 선택자가 한 줄씩 주어진다.

모든 id와 class는 영문 소문자 알파벳으로만 이루어지며 길이는 20 이하다.

각 입력 줄의 길이는 5 000 이하이고, 모든 줄 길이의 합은 5 000 000 이하다.

각 선택자마다 한 줄을 출력한다. 먼저 해당하는 요소 개수를 출력하고, 문서 순서대로 id를 공백으로 구분해 출력한다. 일치하는 요소가 없으면 0만 출력한다.