32361번 - 도서 검색 프로그램

문제

게임개발동아리 PIMM에는 졸업생들이 전공책을 동아리방에 두고 가는 문화가 있다. 과거 PIMM에서는 신입 회원들이 중고 전공책을 자유롭게 사용할 수 있도록 도서 대여 시스템을 운영했다. 하지만 민규가 회장직을 맡았던 작년에는 동아리방에 너무 많은 책이 쌓여 도서 대여 시스템을 관리하기 어렵게 되었고, 이 소식을 들은 종현은 필요한 책들을 바로바로 찾을 수 있도록 하는 도서 검색 프로그램 제작에 착수했다.

종현이 만든 도서 검색 프로그램은 도서와 검색 요청을 각각 문자열 형태로 저장한다는 특징이 있다. 종현이 만든 도서 검색 프로그램 DB에는 도서를 뜻하는 문자열 <book>이 저장된다. <book>은 배커스-나우르 표기법(BNF)에 따라 다음과 같이 표기될 수 있다. 연결된 링크에 서술된 내용과 같이, 테이블의 "::=" 왼쪽에는 기호, 오른쪽에는 표현식이 배치된다.

<book> ::= <name> " " <author> | <name> " " <author> " " <tags>
<tags> ::= <tag> | <tag> " " <tags>
<name> ::= <str>
<author> ::= <str>
<tag> ::= <str>

위 테이블의 기호와 표현식은 아래와 같은 특성을 가진다.

• <str>은 알파벳 대소문자, 숫자, '-', '_'로 이루어진 길이 20ドル$ 이하의 문자열이다.
• <name>은 도서의 이름을 의미한다.
• <author>는 도서의 저자를 의미한다.
• <tag>는 도서가 가진 특징을 의미한다.
• 하나의 <tags> 안에 중복된 <tag>는 존재하지 않는다.

만약 "1984 George_Orwell novel SF"라는 문자열 <book>이 DB 안에 있다면, 이것은 이름이 1984이고 저자가 George_Orwell이며, novel과 SF라는 두 가지 특징을 지닌 도서가 도서 검색 프로그램 안에 있음을 의미한다.

DB 안에 <name>과 <author>가 모두 같은 책이 둘 이상 존재할 수 없다. 단, <name>이나 <author> 둘 중 하나가 일치하는 책이 DB 안에 여러 권 있을 수 있음에 유의하라.

도서 검색 프로그램에 주어지는 검색 요청 <search> 또한 문자열로 주어진다.

<method> ::= <AND> | <OR> | <NOT> | <nameCorrect> | <nameInclude> | <authorCorrect> | <tagCorrect>
<methods> ::= <method> | <method> ", " <methods>
<AND> ::= "A(" <methods> ")"
<OR> ::= "O(" <methods> ")"
<NOT> ::= "N(" <method> ")"
<nameCorrect> ::= "n:" <str>
<nameInclude> ::= "ni:" <str>
<authorCorrect> ::= "a:" <str>
<tagCorrect> ::= "t:" <str>
<search> ::= <methods>

위 테이블의 기호와 표현식은 아래와 같은 특성을 가진다.

• <str>는 알파벳 대소문자, 숫자, '-', '_'로 이루어진 길이 20ドル$ 이하의 문자열이다.
• <nameCorrect>는 표현식 <str>과 주어진 <book>의 <name>이 일치하면 참을, 그렇지 않다면 거짓을 반환하는 기호이다.
• <nameInclude>는 표현식 <str>이 주어진 <book>의 문자열 <name> 안에 포함되었다면 참을, 그렇지 않다면 거짓을 반환하는 기호이다.
• <authorCorrect>는 표현식 <str>과 주어진 <book>의 <author>와 일치하면 참을, 그렇지 않다면 거짓을 반환하는 기호이다.
• <tagCorrect>는 표현식 <str>과 주어진 <book>의 <tags> 안에 일치하는 <tag>가 하나라도 있다면 참을, 그렇지 않다면 거짓을 반환하는 기호이다.
• <AND>는 표현식 <methods> 안의 모든 <method>가 참을 반환하면 참을, 그렇지 않다면 거짓을 반환하는 기호이다.
• <OR>는 표현식 <methods> 안의 <method> 중 하나라도 참을 반환하면 참을, 그렇지 않다면 거짓을 반환하는 기호이다.
• <NOT>은 표현식 <method>가 참을 반환한다면 거짓을, 그렇지 않다면 참을 반환하는 기호이다.
• <search>는 DB 안의 모든 <book>에 대해, 표현식 <methods> 안의 모든 <method>가 참을 반환하는 <book>의 개수를 반환하는 기호이다.

여러 개의 책 <book>과, 여러 개의 문자열 <search>가 주어질 때, 각각의 <search>에 대해 반환되는 값을 한 줄에 하나씩 출력하라.

입력

입력의 첫째 줄에는 DB 안의 문자열 <book>의 개수 $N$이 주어진다. 다음 $N$개 줄에는 DB 안에 저장된 문자열 <book>이 한 줄에 한 개씩 주어진다.

다음 줄에는 검색 요청 문자열인 <search>의 개수 $M$이 주어진다. 다음 $M$개 줄에는 문자열 <search>가 한 줄에 한 개씩 주어진다.

잘못된 문자열은 입력으로 주어지지 않는다.

출력

검색 명령어 <search>에 대한 결괏값을 한 줄에 하나씩 출력한다.

제한

• 1ドル \le N, M \le 200$
• 입력으로 주어지는 문자열 <book>의 길이는 200ドル$보다 작거나 같다.
• 입력으로 주어지는 문자열 <search>의 길이는 1ドル,500円$보다 작거나 같다.
• 입력으로 주어지는 모든 수는 정수이다.

힌트