Recruiting New SCCC Members

Chansol, the president of SCCC, is running the selection process for new members in the first semester of 2023. In that semester, SCCC runs $K$ study groups, each with a capacity of $X$. Each new member must join exactly one of the $K$ study groups. An applicant who cannot join any study group cannot be accepted, so every applicant selects at least one study group they can join.

Chansol gave the $N$ applicants distinct scores after a fair and strict review. To assign the new members to study groups, he sorts the applicants from the highest score to the lowest and assigns them one at a time.

Consider the moment when the applicant with the $i$-th highest score is about to be assigned. If the applicant can be added while keeping the set of people already assigned to the studies, the applicant is assigned. Otherwise, if no seat remains for the applicant no matter how the people already assigned are moved, the applicant cannot be assigned.

For example, let $N=5$, $K=2$, $X=2$, and let the study groups each applicant can join, from the highest score, be $\{1\}, \{1,2\}, \{1\}, \{1\}, \{2\}$.

Suppose the highest and second highest applicants are both assigned to group 1, and the third applicant is next. Move the second applicant to group 2, then assign the third applicant to group 1. The people already assigned remain in the study groups, so the third applicant is accepted.

On the other hand, suppose group 1 holds the first and third applicants and group 2 holds the second applicant. No arrangement lets the fourth applicant be assigned. The lowest-scoring applicant can still join group 2. The final result is that group 1 holds the first and third applicants, and group 2 holds the second and fifth applicants.

Chansol wants to assign the applicants by these rules. Write a program that finds the number of people assigned to study groups and the list of applicants in each study group.

The first line contains the number of applicants $N$, the number of study groups $K$, and the capacity of each study group $X$, separated by spaces.

From the second line onward, the $i$-th of the $N$ lines gives the information for the $i$-th applicant ($1\le i\le N$).

Each line starts with the number of study groups $C_i$ the applicant can join, followed by the $C_i$ study group numbers $A_{i,1},A_{i,2},\cdots ,A_{i,C_i}$, separated by spaces.

The line $N+2$ contains the scores $B_1,B_2,\cdots ,B_N$ of the students, separated by spaces.

Print $K$ lines. The $i$-th line describes group $i$ ($1\le i\le K$).

Each line starts with the number of people assigned to that study group, followed by the numbers of the assigned people, separated by spaces.

If several answers exist, you may print any of them. The order of the assigned people in each line does not matter.

• $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)$
• If $j\ne k$, then $A_{i,j}\ne A_{i,k}$. $(1\le i\le N,1\le j,k\le C_i)$ In other words, every element in a row is distinct.
• $1\leq B_i\leq 10^9$ $(1\le i\le N)$
• If $i\ne j$, then $B_i\ne B_j$. $(1\le i,j\le N)$ In other words, every element of $B$ is distinct.
• All numbers in the input are integers.