C - 決勝進出者 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は、コンテストを開こうと思っています。

コンテストは、 n 回の予選と、 1 回の本選に分かれており、予選の上位 k 人を本選に招待しようと思っています。

本選の出場選手は、以下のように選ばれます。

  • 各予選の最高順位が高い人から順番に選ばれる。
  • 最高順位が同じ場合は、最高順位を取った予選が開かれた時期が早い方から先に選ばれる。
  • k 人が選ばれるまで、この操作を続ける。

高橋君は、招待される選手に出来るだけ早く、本選への招待をしたいです。そこで、予選が終わるたびに、本選への招待が確定した選手に対し、メールを送りたいです。

各予選の結果が与えられるので、予選が終わった際に、誰にメールを送るべきかを求めてください。 なお、本選を辞退する選手はいないものとします。

入力

入力は以下の形式で標準入力から与えられる。

n k
a_{1,1} a_{1,2} ... a_{1,k}
a_{2,1} a_{2,2} ... a_{2,k}
:
a_{n,1} a_{n,2} ... a_{n,k}
  • 1 行目には、予選の回数を表す整数 n (1 ≦ n ≦ 50) と、本選への招待人数を表す整数 k (1 ≦ k ≦ 1000) が、スペース区切りで与えられる。
  • 2 行目から n 行は、各予選での上位 k 人の選手のIDが与えられる。このうち i (1 ≦ i ≦ n) 行目は、i 回目の予選の結果を表す。結果はスペース区切りの k 個の整数で与えられ、このうち j 個目の整数 a_{i,j} (1 ≦ a_{i,j} ≦ 999999)は、i 回目の予選で j 位だった人のIDを表す。なお、p ≠ qのとき、a_{i,p} ≠ a_{i,q}であることが保障されている。

出力

i (1 ≦ i ≦ n) 回目の予選で、予選通過が確定した人のIDの一覧を、i 行目にスペース区切りで出力せよ。予選通過者が複数人いる場合は、IDが小さい順に出力しなさい。 出力の末尾にも改行をいれること。

入力例1

2 11
1 2 3 4 5 6 7 8 9 10 11
1 2 15 14 13 16 17 18 19 20 21

出力例1

1 2 3 4 5 6
7 13 14 15 16

予選が 2 回あります。

まず、1 回目の予選が行われた直後に、上位 6 人は、その後の予選の結果に拠らず、本選への招待が確定します。

次に、2 回目の予選が行われた際、IDが、1,2 の二人の参加者が重複するため、1 回目の予選の 7 位までと、 2 回目の予選の 6 位までの、本選への招待が確定します。

出力順序は、順位に関係なく、IDが若い順であることに注意してください。

入力例2

4 5
1 2 3 4 5
2 1 3 4 5
1 2 3 4 5
2 1 3 4 5

出力例2

1 2

3
4 5

本選への招待者が確定しない予選があることにも注意してください。

Source Name

Code Formula 2014 予選A