University Entrance Examination

Every year a huge number of high-school graduates compete for a limited number of university places through a single, centralized national entrance examination, run by the Education Evaluation Organization (EEO). After the exam, each eligible participant submits a priority list of the Field-Department-University programs (FDUs) they want to join, ordered from most to least preferred. Using each participant's total score, their priority list, and the selection rules below, the EEO fills every FDU up to its capacity. One selection goal is to encourage students to attend universities near their home region, which reduces demand for dormitories. Each accepted participant is placed in exactly one FDU; anyone not placed in any FDU on their list has failed.

You are given $N$ students $S_1, \dots, S_N$ and $M$ programs $F_1, \dots, F_M$. Each student has a total score, a home geographic region (the region where their high-school diploma was awarded), and a priority list of the programs they want. Each program has a geographic region (where its university is located) and a capacity for the year.

Assign students to programs so that both rules below hold.

1. Local-student rule. Consider two students $A$ and $B$ who both listed a program $F$ located in region $R$, and suppose $\mathrm{score}(A) > \mathrm{score}(B)$. If $B$ is local to $F$ (its home region is $R$), $A$ is non-local (home region other than $R$), and $\mathrm{score}(B) > 0.7 \cdot \mathrm{score}(A)$, then $B$ has priority over $A$ for $F$. In every other case $A$ has priority over $B$ for $F$.
2. Fairness rule. Each accepted student is placed in the earliest program on their own priority list that they can actually enter.

All scores are distinct integers.

The first line contains an integer $t$ ($1 \le t \le 10$), the number of test cases. Each test case is given as follows.

The first line contains two integers $N$ ($1 \le N \le 150$) and $M$ ($1 \le M \le 50$).

Each of the next $N$ lines describes one student $S_i$ in the form $R_i \; M_i \; K \; F_{i1} \; \dots \; F_{iK}$, where $R_i$ is the student's home region number, $M_i$ is their exam score, $K$ ($0 \le K \le M$) is the length of their priority list, and $F_{i1}, \dots, F_{iK}$ are the program numbers in order of preference.

Each of the next $M$ lines describes one program $F_j$ as two integers $R_j$ and $C_j$: the region number of $F_j$ and its capacity.

Region numbers are arbitrary integers.

For each test case, print $N$ lines, one per student in input order. On the $i$-th line print $j$ if student $S_i$ is accepted into program $F_j$, or not accepted if the student is not admitted to any program on their list.

Print exactly one blank line between the outputs of consecutive test cases.