ICPC Ranking

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

ICPCの順位付け

ICPC (International Collegiate Programming Contest) の解答提出のログが与えられたとき, 各チームの順位を決定するプログラムを書きなさい.

ログはプログラム提出の記録を提出順に並べたものである. 一つの記録は,経過時間,チーム番号,問題番号,判定結果, の四つの情報からなる. 経過時間は,コンテスト開始から提出までに要した時間を意味する. 判定結果は,プログラムが正解を出したか否か, また不正解だった場合の間違いの種類を表す.

チームの順位は,次に示す規則に従って決められる. なお,この規則は,本物のICPCで使われている規則から 一部の細則を削除して簡単化したものである.

  1. より多くの問題に正解したチームを上位とする.
  2. 正解した問題数が同じ場合は,所要時間合計の少ないチームを上位とする.
  3. 複数のチームが同数の問題に正解し,所要時間合計も同じなら,それらのチームを同順位とする.

所要時間合計とは,正解した問題それぞれの所要時間の合計である. 問題の所要時間とは,その問題に正解したプログラム提出の経過時間に,それ以前に提出された同じ問題に対する不正解一つにつき20分ずつのペナルティを加えたものである.

正解に達しなかった問題の所要時間はゼロと見なされ,不正解がいくつあったとしても,ペナルティは発生しない.

ある問題に正解した後に, 同じ問題に対するプログラムを提出することはないと仮定してよい.

Input

入力は,次の形式のデータセットの集まりである. 最後のデータセットの直後には,四つのゼロからなる行がある.

M T P R
m1 t1 p1 j1
m2 t2 p2 j2
.....
mR tR pR jR

データセットの最初の行には,MTPRの 四つの整数が与えられる. Mは,コンテストの始まりから終わりまでの時間である. Tは,チーム数である. Pは,問題数である. Rは,提出記録の数である. これらの値に関して, 120 ≤ M ≤ 300, 1 ≤ T ≤ 50, 1 ≤ P ≤ 10, 0 ≤ R ≤ 2000 が成り立つ. 各チームには1からTまでのチーム番号が与えられ, 各問題には1からPまでの問題番号が与えられている.

2行目からのR行に,1行一つの形式で提出記録が与えられる. 各提出記録の記述は, mktkpkjk の四つの整数からなる(1 ≤ k ≤ R). mkは,経過時間である. tkは,チーム番号である. pkは,問題番号である. jkは,判定結果を表す(0なら正解,0以外なら不正解). これらの値に関して, 0 ≤ mk ≤ M−1, 1 ≤ tk ≤ T, 1 ≤ pk ≤ P, 0 ≤ jk ≤ 10 が成り立つ.

経過時間は分単位に切り捨てられている.

提出記録は,提出された順番に従って与えられる. したがって,i < jなら, i番の提出はj番の提出より先に行われたものである (mi ≤ mj). このことを利用すると,二つのチームの所要時間合計の分未満の差の正負を 推定できる場合があるが, このような情報を順位決定に利用することはない. 各チームの順位は,分単位の時間情報だけに基づいて決める.

Output

各データセットに対して,1からTまでのチーム番号を 上位から順に1行に並べて出力しなさい. チーム番号間の区切り記号はコンマとする. ただし,同順位のチームの間の区切り記号はイコールとする. 同順位のチームは,チーム番号の大きいものから順に(降順に)並べること.

Sample Input

300 10 8 5
50 5 2 1
70 5 2 0
75 1 1 0
100 3 1 0
150 3 2 0
240 5 5 7
50 1 1 0
60 2 2 0
70 2 3 0
90 1 3 0
120 3 5 0
140 4 1 0
150 2 4 1
180 3 5 4
15 2 2 1
20 2 2 1
25 2 2 0
60 1 1 0
120 5 5 4
15 5 4 1
20 5 4 0
40 1 1 0
40 2 2 0
120 2 3 4
30 1 1 0
40 2 1 0
50 2 2 0
60 1 2 0
120 3 3 2
0 1 1 0
1 2 2 0
300 5 8 0
0 0 0 0

Output for the Sample Input

3,1,5,10=9=8=7=6=4=2
2,1,3,4,5
1,2,3
5=2=1,4=3
2=1
1,2,3
5=4=3=2=1

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Aizu, Japan, 2013-07-12
http://sparth.u-aizu.ac.jp/icpc2013/