루미 알고리즘

#1485플래티넘Identifying Cells

PO 2020 결선코딩출제 Karl Lundstig, Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

After receiving yet another Wrong Answer verdict, even though your program was guaranteed to be completely correct this time, you have decided to take a break from competitive programming. You are now studying biology instead, more specifically, you are interested in the cells of your favorite cactus (their green color reminds you of Accepted verdicts).

In the sample you are looking at, unfortunately, there are all sorts of cells, and it's not entirely easy to know if you are really looking at your favorites. Different types of cells have different components that they can be identified by. For example, most cells have Golgi apparatuses, but only plant cells have vacuoles. Identification is further complicated by the fact that your cheap microscope doesn't always manage to see all the components in a cell.

Your biology book describes the components of N different cell types. There are a total of K possible components, and no two cell types consist of exactly the same parts.

In order to aid your research, you will create a program that, given the components that you can see in a given cell, will attempt to identify its type. Because there are so many cells in your sample, it needs to do this Q times.

Input

The first line of the input contains the integers N and K (1 ≤ N ≤ 2 · 10^5, 1 ≤ K ≤ 21), the number of cell types in your book and the number of possible components.

The following N lines each describe a cell type from your book, the first line describing the first one, the second line describes the second one and so on. Each line contains a string containing K ones or zeros, where the i:th character is a one if the cell type contains component i.

The next line contains a single integer Q (1 ≤ Q ≤ 2 · 10^5), the number of queries.

The following Q lines each describe a query. Each line contains a description of the components you can see in the microscope, in the same format as the cells in your book. A one in position i means that you know that the cell you are looking at has component i. However, it may be the case that the cell contains more components that you can't see with your microscope. Also note that it is possible that two different cells both have a certain component, but you are only able to see it in one of them.

Output

For each query, you should print a line containing the answer.

  • If the cell type can be decided unambiguously, print the index 1 ≤ i ≤ N of the type of the cell.
  • If there are multiple possibilites, you should print “vet ej” (don't know).
  • If there are no matching cell types, you should print “finns ej” (doesn't exist).

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
115K ≤ 8, N, Q ≤ 10
230N, Q ≤ 1000
355No additional constraints.

예제

예제 1

입력
3 4
1000
0110
1101
5
1000
1100
1001
0110
1010
출력
vet ej
3
3
2
finns ej

출처 표기

출처: Programmeringsolympiaden 2020년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.