─점심시간─

시간 제한1.5초메모리 제한1024 MB

요약
여러 장르를 나열한 질문마다 그 장르에 모두 속하는 책이 몇 권인지 센다.
난이도

보통10점 중 5점

유형
비트 연산, 해시맵, 완전 탐색
정답자
아직 제출이 없습니다

문제

짐비는 점심시간에 도서관에서 책을 읽는 것을 좋아합니다. 짐비네 학교 도서관에는 총 MM권의 책이 비치되어 있습니다. 도서관에 있는 각 책은 NN가지의 장르 중 하나 이상에 속해 있다고 합니다.

다독왕 짐비는 장르를 하나 이상 떠올린 뒤, 그 장르에 모두 속하는 책만을 골라서 읽으려고 합니다. 도서관에 있는 모든 책을 찾아보다가 지쳐버린 짐비를 위해, 아래와 같은 짐비의 질문에 QQ번 답하는 프로그램을 작성해 주세요.

  • 짐비가 떠올린 xx개의 장르 c_1,c\_1, c_2,c\_2, ⋯ ,\cdots, c_xc\_x에 모두 포함되는 책은 몇 권일까요?

입력

첫 번째 줄에 장르의 수를 나타내는 정수 NN이 주어집니다. (1≤N≤200)(1 \leq N \leq 200)

두 번째 줄에 장르를 나타내는 영어 알파벳 소문자로 구성된 서로 다른 NN개의 문자열 g_1,g\_1, g_2,g\_2, ⋯ ,\cdots, g_Ng\_N이 공백을 간격으로 주어집니다. (1≤∣g_i∣≤20)(1\le |g\_i|\le 20)

세 번째 줄에 책의 수를 나타내는 정수 MM가 주어집니다. (1≤M≤5,000)(1 \leq M \leq 5\\,000)

이후 MM개의 줄에 걸쳐 총 MM권의 책의 정보가 한 줄에 하나씩 K_i,K\_i, n_i,n\_i, b_i,1,b\_{i,1}, b_i,2,b\_{i,2}, ⋯ ,\cdots, b_i,K_ib\_{i,K\_i}의 형태로 주어집니다. K_iK\_i는 ii번째 책에 해당하는 장르의 수를 나타내는 정수, n_in\_i는 ii번째 책의 제목을 나타내는 영어 알파벳 소문자로 구성된 문자열, b_i,1,b\_{i,1}, b_i,2,b\_{i,2}, ⋯ ,\cdots, b_i,K_ib\_{i,K\_i}는 ii번째 책에 해당하는 장르를 나타내는 서로 다른 문자열입니다. 모든 책의 제목은 서로 다릅니다. (1≤K_i≤N;(1\le K\_i\le N; 1≤∣n_i∣≤20)1\le|n\_i|\le 20)

그다음 줄에 질문의 개수 QQ가 주어집니다. (1≤Q≤5,000)(1 \leq Q \leq 5\\,000)

이후 QQ개의 줄에 걸쳐 질문이 x,x, c_1,c\_1, c_2,c\_2, ⋯ ,\cdots, c_xc\_x의 형태로 한 줄에 하나씩 공백을 간격으로 주어집니다. 한 질문에서 주어지는 장르는 서로 다릅니다. (1≤x≤N)(1\leq x\leq N)

입력으로 주어지는 모든 장르는 두 번째 줄에 주어진 NN개의 장르 중 하나입니다. 즉, b_i,j,c_i∈g_1,g_2,⋯ ,g_Nb\_{i,j}, c\_{i} \in \\{g\_1, g\_2, \cdots, g\_N\\}입니다.

출력

QQ개의 줄에 걸쳐 각 질문에 대한 답을 한 줄에 하나씩 차례대로 출력해 주세요.

예제1

  1. 예제 1

    입력
    5
    fantasy mystery romance scifi horror
    7
    2 bookone fantasy mystery
    1 booktwo scifi
    3 bookthree fantasy scifi horror
    2 bookfour mystery horror
    1 bookfive romance
    2 booksix fantasy romance
    3 bookseven fantasy mystery romance
    3
    2 fantasy scifi
    1 romance
    3 mystery romance horror
    
    예상 출력
    1
    3
    0