Selecting Teams Advanced to Regional

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem 03: Selecting Teams Advanced to Regional

日本で毎年開催される国際大学対抗プログラミングコンテストのアジア地区予選に出場するためには、厳しい国内予選を突破しなければなりません。

大学対抗とは言っても、1つの学校から複数のチームが参戦します。そこで、できるだけ多くの学校がアジア地区予選に出場できるように、突破チームの選抜には以下の選抜ルールが適用されます:

該当チームを A とし、成績の優秀な順番に次のルールを適用します:

  • ルール 1:
    その時点での選抜チーム数が 10 に満たない場合:
    A と同じ所属でその時点で選抜されたチームの数が 3 に満たなければ、A は選抜されます。
  • ルール 2:
    その時点での選抜チーム数が 20 に満たない場合:
    A と同じ所属でその時点で選抜されたチームの数が 2 に満たなければ、A は選抜されます。
  • ルール 3:
    その時点での選抜チーム数が 26 に満たない場合:
    A と同じ所属でその時点で選抜されたチームがなければ、A は選抜さます。

また、成績の順番は次のルールで決定されます:

  • より多くの問題を解いたチームが上位となります。
  • 解いた問題数が同じ場合は、ペナルティが小さいチームが上位となります。

各チームのID(整数)、所属(整数)、正解数(整数)、ペナルティ(整数)を入力し、選抜チームのIDを選抜順に出力するプログラムを作成して下さい。 チームは成績順に与えられるとは限らないので、順位付けした後、選抜ルールを適用しなければならないことに注意して下さい。

この問題では、正解数とペナルティが同じチームがあった場合はIDが小さい方を上位とします。

Input

複数のデータセットが入力として与えられます。各データセットは以下の形式で与えられます:

n (チーム数:整数)
I1 U1 A1 P1 (1番目のチームのID、所属、正解数、ペナルティ:空白区切りの4つの整数)
I2 U2 A2 P2 (2番目のチームのID、所属、正解数、ペナルティ:空白区切りの4つの整数)
.
.
In Un An Pn (n番目のチームのID、所属、正解数、ペナルティ:空白区切りの4つの整数)

n は 300 以下であり、Ii, Ui は 1 以上 1000 以下とします。1つのデータセットに、同じ ID のチームは無いと仮定してかまいません。

Ai は 10 以下、Pi は 100,000 以下とします。

n が 0 のとき、入力の終わりとします。

Output

各データセットについて、選抜チームのIDを選抜された順に出力して下さい。1つのIDを1行に出力して下さい。

Sample Input

6
1 1 6 200
2 1 6 300
3 1 6 400
4 2 5 1200
5 1 5 1400
6 3 4 800
3
777 1 5 300
808 2 4 20
123 3 6 500
2
2 1 3 100
1 1 3 100
0

Output for the Sample Input

1
2
3
4
6
123
777
808
1
2

Source: PC Koshien 2009 Warm-Up Contest , Aizu-Wakamatsu, Japan, 2009-08-22