問題文

ある回の MMA Contest に $N$ 人が参加しました。

この回は $M$ 問体制で、問題ごとに配点の違いはありません。$\\$ $i$ 人目の参加者は、$S_i$ という ID で参加し、$j$ 問目の問題をコンテスト開始から $T_{i, j}$ 秒で解きました。 順位は以下のルールで決められます。

• 問題を多く解いた人の方が高い
• 解いた問題数が同じときは、最後に正解した問題の提出時間が早いほど高い
• それでも $i$ 人目の参加者と $j$ 人めの参加者の順位が同じになる場合、 $i < j$ を満たす $i$ 人目の参加者の方が順位が高いとする

以上のルールで順位を求めた後、順位が高い順に ID を出力してください。

制約

• $S_i$ はアルファベット小文字のみからなる
• $1 \leq |S_i| \leq 10$
• $N, M, T_{i, j}$ はすべて整数
• $1 \leq N \leq 1000$
• $1 \leq M \leq 10$
• $1 \leq T_{i, j} \leq 6000$ もしくは $T_{i, j} = -1$
• $T_{i, j} = -1$ のとき、$i$ 人目の参加者は $j$ 問目を解けていない
• $i \neq j$ ならば $S_i \neq S_j$

入力

入力は以下の形式で与えられます。

出力

計算結果を一行に出力せよ。

サンプル

3 5
dyktr 72 231 425 1157 3751
sepa 24 81 257 747 -1
ryota 96 283 591 1849 -1

dyktr
sepa
ryota

5 3
a -1 -1 129
b 59 195 598
c 181 1193 -1
d -1 -1 -1
e 296 -1 1193

b
c
e
a
d