S10

commons.wikimedia.org에서 가져온 사진

On Suðurlandsbraut에는 그곳에 입주한 회사들에 볼일이 있는 사람이 많아 주차 공간을 찾기 어려울 수 있다. 주차 공간의 상당수는 이 회사들의 고객용이라고 명시되어 있으며 단기 주차만 허용된다. 따라서 한 번에 15--30분 동안만 이용할 수 있다. 회사 직원들은 이 주차 공간들을 이용할 수 없으므로, 회사들은 일부 주차 공간이 직원용으로 확보되도록 해야 한다.

Suðurlandsbraut 10 옆에는 주차 공간이 많은 삼층 주차장이 있다. 주차 공간이 매우 많지만 모두 사용 중일 수도 있다. 추가 차량은 주차 공간이 아닌 곳, 예를 들어 다른 주차 공간 앞이나 입구 옆에 불법으로 주차될 수 있다. 회사들이 주차장을 함께 사용하므로 주차 공간은 회사별로 배분되어 있다. 주차 공간에는 어느 회사의 것인지 명시적으로 표시되어 있지 않다. 직원들은 주차장에 자유롭게 주차할 수 있으며, 각 회사에는 동시에 사용할 수 있는 주차 공간 수의 한도가 있다. 주차장 입구의 카메라는 출입하는 각 차량의 번호판을 촬영한다. 차량을 밤새 주차장에 세워 둘 수 없으므로 매일 시작할 때 주차장은 항상 비어 있다.

주차장에 들어오는 각 차량은 다음 규칙에 따라 합법 또는 불법으로 주차한다.

• 빈 주차 공간이 있으면 차량은 그 주차 공간에 주차하고, 그렇지 않으면 주차 공간이 아닌 곳에 불법으로 주차한다.

• 차량의 번호판이 어느 회사에도 등록되어 있지 않다면, 주차 공간에 주차했는지와 관계없이 불법 주차한다.

• 차량의 번호판이 어떤 회사에 등록되어 있고, 같은 회사가 배정받은 주차 공간 할당량에 도달했다면 차량은 불법 주차한다.

주차 공간에 주차된 차량만 해당 번호판이 등록된 회사의 할당량에 포함된다.

Eyþór는 Karlar & Kanínur 유한회사의 프로그래머이며, 자신이 주차 공간을 전혀 찾을 수 없다는 사실을 매우 이상하게 여긴다. 그의 회사에서는 차량을 이용하는 직원이 많지 않기 때문에 그는 수상한 일이 벌어지고 있다고 의심한다. 누군가 불법 주차를 하고 있는 것이 틀림없다. 그는 누가 규칙을 어기고 있는지 알아내기 위해 카메라의 데이터를 이용하자는 생각을 떠올린다.

Eyþór는 건물주에게 어제 카메라가 촬영한 사진을 요청한다. 또한 각 회사에 등록된 번호판 목록도 요청한다. 요청한 정보를 받은 뒤, 그는 데이터 처리를 더 쉽게 하려고 사진을 스캔하여 텍스트 기록으로 변환하는 프로그램을 작성한다.

이런! Eyþór는 오늘 예정된 일곱 번의 회의 중 겨우 첫 회의인 일일 스크럼 회의에 늦었다는 것을 깨닫는다. Eyþór가 오늘 혼자서 범인들을 잡을 기회는 없을 듯하여, 이 작업을 마치는 데 당신의 도움을 요청한다. Eyþór를 위해 데이터 처리를 마치고 불법 주차한 모든 차량의 번호판을 찾아낼 수 있는가?

채점

그룹 | 점수 | 제한

1 | 10 | $1 \leq n \leq 100$, $1 \leq k \leq 10$, $1 \leq m \leq 200$, 모든 차량은 주차 공간에 주차되어 있음

   |          |  또한 모든 회사가 각자의 할당량을 준수함

2 | 15 | $1 \leq n \leq 100$, $1 \leq k \leq 10$, $1 \leq m \leq 200$, 모든 차량은 주차 공간에 주차되어 있음

3 | 15 | $1 \leq n \leq 100$, $1 \leq k \leq 10$, $1 \leq m \leq 200$, 모든 회사가 각자의 할당량을 준수함

4 | 15 | $1 \leq n \leq 100$, $1 \leq k \leq 10$, $1 \leq m \leq 200$

5 | 15 | $1 \leq n \leq 10^5$, $1 \leq k \leq 10^4$, $1 \leq m \leq 2 \cdot 10^5$, 모든 차량은 주차 공간에 주차되어 있음

6 | 15 | $1 \leq n \leq 10^5$, $1 \leq k \leq 10^4$, $1 \leq m \leq 2 \cdot 10^5$, 모든 회사가 각자의 할당량을 준수함

7 | 15 | $1 \leq n \leq 10^5$, $1 \leq k \leq 10^4$, $1 \leq m \leq 2 \cdot 10^5$

입력의 첫째 줄에는 주차장의 주차 공간 수인 $n$과 주차장을 사용하는 회사 수인 $k$, 두 정수가 주어진다.

이어서 각 회사에 대해 하나씩, $k$개의 설명이 주어진다. 각 회사 $i$의 설명은 회사 $i$에 배정된 주차 공간 수인 $n_i$과 회사 $i$에 등록된 번호판 수인 $m_i$, 두 정수로 이루어진 줄로 시작한다. 그 뒤에 각각 하나의 번호판으로 이루어진 $m_i$개의 줄이 주어진다.

이어서 카메라가 촬영한 사진 수인 정수 $m$ 하나로 이루어진 줄이 주어진다. 마지막으로 카메라가 사진을 촬영한 순서대로, 각각 사진 하나를 나타내는 $m$개의 줄이 주어진다. 각 줄은 하나의 번호판으로 이루어진다.

입력의 각 번호판은 두 개 이상 여섯 개 이하의 기호로 이루어지며, 모든 기호는 영문 대문자 또는 숫자이다. 모든 $i$에 대해 $0 \leq n_i \leq n$임이 보장되며, 회사들에 배정된 주차 공간 수의 합은 주차장의 주차 공간 수보다 크지 않다고 가정해도 된다. 회사들에 등록된 번호판 수는 주차 공간 수의 최대 두 배이다. 또한 하나의 번호판이 서로 다른 두 회사에 등록되거나 같은 회사에 두 번 등록되는 일은 없다고 가정해도 된다. 입력에 등장하는 번호판의 총개수는 최대 $4 \cdot 10^5$개이다.

먼저 프로그램이 출력할 번호판 수를 나타내는 정수 하나를 출력한다. 그런 다음 적어도 한 번 불법 주차한 모든 차량의 번호판을 출력한다. 번호판은 사전순으로 출력해야 한다.