세포 식별하기

이번에는 프로그램이 완전히 정확하다고 장담했는데도 또다시 Wrong Answer 판정을 받은 뒤, 당신은 경쟁 프로그래밍을 잠시 쉬기로 했다. 이제는 대신 생물학을 공부하고 있으며, 더 구체적으로는 당신이 가장 좋아하는 선인장의 세포에 관심이 있다(세포의 초록색을 보면 Accepted 판정이 떠오른다).

안타깝게도 살펴보고 있는 표본에는 온갖 종류의 세포가 있어서, 실제로 자신이 좋아하는 세포를 보고 있는지 알아내기가 그리 쉽지 않다. 세포의 종류마다 식별에 사용할 수 있는 구성 요소가 다르다. 예를 들어, 대부분의 세포에는 골지체가 있지만 액포는 식물 세포에만 있다. 게다가 값싼 현미경으로는 세포의 모든 구성 요소가 항상 보이지 않기 때문에 식별이 더욱 복잡해진다.

당신의 생물학 책에는 서로 다른 세포 유형 $N$개의 구성 요소가 설명되어 있다. 가능한 구성 요소는 총 $K$개이며, 정확히 같은 구성 요소로 이루어진 두 세포 유형은 없다.

연구를 돕기 위해, 주어진 세포에서 볼 수 있는 구성 요소가 주어졌을 때 그 유형을 식별하려고 시도하는 프로그램을 작성한다. 표본에 세포가 매우 많으므로 이 작업을 $Q$번 수행해야 한다.

채점

해답은 여러 테스트 그룹으로 이루어진 집합에 대해 채점되며, 각 테스트 그룹에는 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 한 테스트 그룹의 점수를 받으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한

$1$ |$15$| $K \le 8$, $N, Q \leq 10$

$2$ |$30$| $N, Q \leq 1000$

$3$ |$55$| 추가 제한 없음.

입력의 첫째 줄에는 책에 있는 세포 유형의 수와 가능한 구성 요소의 수를 나타내는 정수 $N$와 $K$가 주어진다($1 \leq N \leq 2 \cdot 10^5$, $1 \leq K \leq 21$).

이어지는 $N$개의 줄에는 각각 책에 있는 세포 유형 하나가 설명되며, 첫째 줄은 첫 번째 유형, 둘째 줄은 두 번째 유형을 설명하는 식으로 이어진다. 각 줄에는 일 또는 영 $K$개로 이루어진 문자열이 주어지며, 세포 유형이 구성 요소 $i$를 포함하면 $i$:번째 문자가 일이다.

다음 줄에는 질의의 수를 나타내는 정수 $Q$ 하나가 주어진다($1 \leq Q \leq 2\cdot 10^5$).

이어지는 $Q$개의 줄에는 각각 질의 하나가 설명된다. 각 줄에는 현미경으로 볼 수 있는 구성 요소의 설명이 책에 있는 세포와 같은 형식으로 주어진다. 위치 $i$에 있는 일이 의미하는 것은 살펴보고 있는 세포에 구성 요소 $i$가 있다는 사실을 알고 있다는 것이다. 하지만 그 세포에는 현미경으로 볼 수 없는 구성 요소가 더 있을 수도 있다. 또한 서로 다른 두 세포에 특정 구성 요소가 모두 있더라도, 그 구성 요소가 한 세포에서만 보일 수도 있다는 점에 유의한다.

각 질의마다 답을 한 줄에 출력한다.

• 세포 유형을 모호함 없이 결정할 수 있다면, 그 세포 유형의 인덱스 $1 \leq i \leq N$를 출력한다.

• 가능한 유형이 여러 개라면 ```vet ej`'' (알 수 없음)를 출력한다.

• 일치하는 세포 유형이 없다면 ```finns ej`'' (존재하지 않음)를 출력한다.