ACM-UCPC

2020년, 태양계 지구의 전산학 학회인 ACM(Association for Computing Machinery)이 대학생 프로그래밍 경시대회 ACM-UCPC(Universal Collegiate Programming Contest)를 연다. 시간과 장소의 제약 때문에 예선은 인터넷으로 치른다.

예선이 끝나면 각 팀의 성적이 푼 문제 수와 페널티로 주어진다. 문제를 더 많이 푼 팀이 순위에서 앞서고, 푼 문제 수가 같으면 페널티가 적은 팀이 앞선다. 어떤 두 팀도 순위가 같지 않다. 순위대로 정렬된 예선 결과를 받아 본선에 나갈 60팀을 뽑는 프로그램을 작성하시오.

성적이 우수한 팀을 뽑되 한 학교에서 너무 많은 팀이 뽑히지 않도록, 순위가 높은 팀부터 차례대로 아래 규칙을 적용해 선발 여부를 정한다. 지금 보고 있는 팀의 학교에서 이미 선발된 팀 수를 $k$, 그 학교가 예선에 낸 팀 수를 $M$이라 하자.

1. $k$가 $\lceil M/2 \rceil$ 이상이면 선발하지 않는다. 즉 한 학교에서 최대 $\lceil M/2 \rceil$팀까지만 뽑는다. 2팀이 참가했으면 최대 1팀, 3팀이 참가했으면 최대 2팀이다.
2. 지금 보고 있는 팀의 전체 순위가 1위부터 10위까지이면 $k \le 3$일 때만 선발한다.
3. 전체 순위가 11위부터 20위까지이면 $k \le 2$일 때만 선발한다.
4. 전체 순위가 21위부터 30위까지이면 $k \le 1$일 때만 선발한다.
5. 전체 순위가 31위 이하이면 $k = 0$일 때만 선발한다.

선발된 팀이 60팀이 되면 그 자리에서 멈춘다. 규칙을 끝까지 적용하고도 60팀을 채우지 못하면, 아직 선발되지 않은 팀 중에서 순위가 앞선 팀부터 차례대로 뽑아 60팀을 채운다. 이렇게 채울 때는 위 규칙을 적용하지 않는다. 참가 팀이 60팀보다 적으면 모든 팀을 선발한다.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫 줄에는 참가 팀의 수 $N$ ($1 \le N \le 1000$)이 주어지고, 이어지는 $N$개의 줄에 팀 이름 team, 학교 이름 school, 푼 문제 수 solved, 페널티 penalty가 공백 하나로 구분되어 주어진다 ($1 \le solved \le 10$, $1 \le penalty \le 10000$). team과 school은 공백이 없는 길이 20 이하의 문자열이다. 각 테스트 케이스의 $N$개 줄은 순위가 높은 팀부터 차례대로 주어진다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 선발된 팀 중 전체 순위가 가장 낮은 팀의 이름을 한 줄에 하나씩 출력한다.