SCCC 신입 부원 모집하기

SCCC의 회장인 찬솔이는 2023년 1학기 신입 부원 선발을 진행하고 있다. SCCC는 2023년 1학기에 정원이 $X$명인 스터디 그룹을 $K$개 운영하며, 새로 들어오는 신입 부원은 $K$개의 스터디 그룹 중 정확히 하나에 참가해야 한다. 참가할 수 있는 스터디 그룹이 없으면 합격할 수 없으므로, 모든 지원자는 참가할 수 있는 스터디 그룹을 한 개 이상 골라 두었다.

찬솔이는 공정하고 엄격한 심사를 거쳐 $N$명의 지원자에게 서로 다른 점수를 매겼다. 신입 부원을 스터디 그룹에 배정하기 위해 점수가 높은 사람부터 낮은 사람 순으로 정렬한 뒤, 한 명씩 배정하려고 한다.

점수가 $i$번째로 높은 사람을 배정하는 상황을 생각해 보자. 지금까지 스터디에 배정된 사람들의 집합을 그대로 유지하면서 $i$번째 사람을 넣을 수 있으면 그 사람을 배정한다. 반대로 지금까지 배정된 사람들을 어떻게 옮기더라도 $i$번째 사람이 들어갈 자리가 없으면 그 사람은 배정되지 않는다.

예를 들어 $N=5$, $K=2$, $X=2$이고, 점수가 높은 사람부터 참가할 수 있는 스터디 그룹이 $\{1\}, \{1,2\}, \{1\}, \{1\}, \{2\}$라고 하자.

점수가 가장 높은 사람과 두 번째로 높은 사람이 모두 1번 그룹에 배정되었고, 세 번째 사람을 배정해야 한다고 하자. 두 번째 사람을 2번 그룹으로 옮기고 세 번째 사람을 1번 그룹에 배정하면, 지금까지 배정된 집합을 유지하면서 세 번째 사람을 넣을 수 있다.

반면 1번 그룹에 첫 번째와 세 번째 사람, 2번 그룹에 두 번째 사람이 있는 상태에서는 네 번째 사람을 배정할 방법이 없다. 하지만 점수가 가장 낮은 사람은 2번 그룹에 들어갈 수 있다. 최종 결과는 1번 그룹에 첫 번째와 세 번째 사람, 2번 그룹에 두 번째와 다섯 번째 사람이 배정되는 것이다.

찬솔이는 이 규칙에 따라 지원자를 스터디 그룹에 배정하려고 한다. 스터디 그룹에 배정되는 사람의 수와 각 스터디 그룹에 배정된 지원자의 목록을 구하는 배정 프로그램을 작성하자.

첫째 줄에 지원자 수 $N$, 스터디 그룹의 개수 $K$, 각 스터디 그룹의 정원 $X$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 지원자의 정보가 주어진다. ($1\le i\le N$)

지원자의 정보는 한 줄로 주어진다. 줄의 처음에는 참가할 수 있는 스터디 그룹의 개수 $C_i$가 주어지고, 이어서 참가할 수 있는 $C_i$개의 스터디 그룹 번호 $A_{i,1},A_{i,2},\cdots ,A_{i,C_i}$가 공백으로 구분되어 주어진다.

$N+2$번째 줄에는 각 학생의 점수 $B_1,B_2,\cdots ,B_N$이 공백으로 구분되어 주어진다.

첫째 줄부터 $K$개의 줄에 걸쳐, $i$번째 줄에 $i$번 그룹에 배정된 사람의 정보를 출력한다. ($1\le i\le K$)

각 줄의 처음에는 해당 스터디 그룹에 배정된 사람의 수를 출력하고, 이어서 배정된 사람의 번호를 공백으로 구분하여 출력한다.

답이 여러 개이면 아무거나 출력해도 된다. 배정된 사람의 번호를 출력하는 순서는 상관없다.

• $1\leq N,K,X\leq 15$
• $1\leq K\times X\leq 15$
• $1\leq C_i\leq K$
• $1\leq A_{i,j}\leq K$ $(1\le i\le N,1\le j\le C_i)$
• $j\ne k$이면 $A_{i,j}\ne A_{i,k}$이다. $(1\le i\le N,1\le j,k\le C_i)$ 즉, 각 행의 원소는 모두 서로 다르다.
• $1\leq B_i\leq 10^9$ $(1\le i\le N)$
• $i\ne j$이면 $B_i\ne B_j$이다. $(1\le i,j\le N)$ 즉, $B$의 원소는 모두 서로 다르다.
• 입력으로 주어지는 수는 모두 정수이다.