대학 입학 시험

매년 수많은 고교 졸업생이 하나의 중앙집중식 국가 시험을 통해 제한된 대학 정원을 두고 경쟁한다. 이 시험은 교육평가기관(EEO)이 주관한다. 시험이 끝나면 지원 자격을 갖춘 각 지원자는 들어가고 싶은 학과-전공-대학(FDU) 프로그램들을 선호하는 순서대로 나열한 지망 목록을 제출한다. 평가기관은 각 지원자의 총점, 지망 목록, 그리고 아래 선발 규칙을 이용해 모든 FDU를 정원만큼 채운다. 선발의 한 가지 목표는 학생들이 출신 지역 근처의 대학에 진학하도록 유도해 기숙사 수요를 줄이는 것이다. 합격한 지원자는 정확히 하나의 FDU에만 배정되며, 자신의 목록에 있는 어떤 FDU에도 배정되지 못한 지원자는 불합격이다.

학생 $N$명 $S_1, \dots, S_N$과 프로그램 $M$개 $F_1, \dots, F_M$이 주어진다. 각 학생은 총점, 출신 지역(고등학교 졸업장을 받은 지역), 그리고 지원하고 싶은 프로그램들의 지망 목록을 가진다. 각 프로그램은 소재 지역(대학이 위치한 지역)과 그 해의 정원을 가진다.

아래 두 규칙을 모두 만족하도록 학생들을 프로그램에 배정하라.

1. 지역 학생 규칙. 두 학생 $A$와 $B$가 모두 지역 $R$에 있는 프로그램 $F$를 지망했고 $\mathrm{score}(A) > \mathrm{score}(B)$라고 하자. 만약 $B$가 $F$에 대해 지역 학생이고(출신 지역이 $R$), $A$는 비지역 학생이며(출신 지역이 $R$이 아님), $\mathrm{score}(B) > 0.7 \cdot \mathrm{score}(A)$이면 $F$에 대해 $B$가 $A$보다 우선한다. 그 밖의 모든 경우에는 $A$가 $B$보다 우선한다.
2. 공정성 규칙. 합격한 각 학생은 자신의 지망 목록에서 실제로 들어갈 수 있는 가장 앞선 프로그램에 배정된다.

모든 점수는 서로 다른 정수이다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$)가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

첫 줄에 두 정수 $N$ ($1 \le N \le 150$)과 $M$ ($1 \le M \le 50$)이 주어진다.

이어지는 $N$개의 줄에는 각 학생 $S_i$의 정보가 $R_i \; M_i \; K \; F_{i1} \; \dots \; F_{iK}$ 형식으로 주어진다. 여기서 $R_i$는 학생의 출신 지역 번호, $M_i$는 시험 점수, $K$ ($0 \le K \le M$)는 지망 목록의 길이이며, $F_{i1}, \dots, F_{iK}$는 선호 순서대로 나열한 프로그램 번호이다.

그 다음 $M$개의 줄에는 각 프로그램 $F_j$의 정보가 두 정수 $R_j$와 $C_j$로 주어지며, 각각 $F_j$의 지역 번호와 정원을 의미한다.

지역 번호는 임의의 정수이다.

각 테스트 케이스에 대해 입력 순서대로 학생마다 한 줄씩, 총 $N$개의 줄을 출력한다. $i$번째 줄에는 학생 $S_i$가 프로그램 $F_j$에 합격했다면 $j$를, 목록의 어떤 프로그램에도 합격하지 못했다면 not accepted를 출력한다.

연속한 테스트 케이스의 출력 사이에는 정확히 한 개의 빈 줄을 넣는다.