配点 : $300$ 点

問題文

$1$ から $2N$ の番号がついた $2N$ 人でじゃんけん大会をします。

大会は $M$ ラウンドからなり、各ラウンドは、全ての人が $1$ 度ずつ参加するような $1$ 対 $1$ の $N$ 試合からなります。

$i=0,1,\ldots,M$ について、$i$ ラウンド目の終了時点での順位を次のように決めます。

• $i$ ラウンド目までの勝数が多い方が上位
• $i$ ラウンド目までの勝数が同じときは、番号が小さい方が上位

また、$i=1,\ldots,M$ について、$i$ ラウンド目の各試合の組み合わせを次のように決めます。

• 各 $k=1,2,\ldots,N$ について、$i-1$ ラウンド目終了時点の順位が $2k-1$ 位の人と $2k$ 位の人が試合をする

各試合では、対戦する $2$ 人がそれぞれ $1$ 度だけ手を出し、勝ち・負け・引き分けのいずれかの結果が発生します。

未来予知ができる高橋君は、人 $i$ が $j$ ラウンド目の試合で出す手が $A_{i,j}$ であることを知っています。 $A_{i,j}$ は G, C, P のいずれかであり、それぞれグー、チョキ、パーを表します。

$M$ ラウンド目終了時点の順位を求めてください。

制約

• $1 \leq N \leq 50$
• $1 \leq M \leq 100$
• $A_{i,j}$ は G, C, P のいずれか

入力

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

$N$ $M$

$A_{1,1}A_{1,2}\ldots A_{1,M}$

$A_{2,1}A_{2,2}\ldots A_{2,M}$

$\vdots$

$A_{2N,1}A_{2N,2}\ldots A_{2N,M}$

出力

$2N$ 行出力せよ。

$i$ 行目には、$M$ ラウンド目終了時点での順位が $i$ 位である人の番号を出力せよ。

2 3
GCP
PPP
CCC
PPC

3
1
2
4

$1$ ラウンド目では人 $1$ と $2$、$3$ と $4$ がそれぞれ試合をし、前者の試合は人 $2$ が、後者の試合は人 $3$ が勝ちます。 $2$ ラウンド目では人 $2$ と $3$、$1$ と $4$ がそれぞれ試合をし、前者の試合は人 $3$ が、後者の試合は人 $1$ が勝ちます。 $3$ ラウンド目では人 $3$ と $1$、$2$ と $4$ がそれぞれ試合をし、前者の試合は人 $3$ が、後者の試合は人 $4$ が勝ちます。 よって最終的な順位は、上位から順に人 $3,1,2,4$ となります。

2 2
GC
PG
CG
PP

1
2
3
4

$1$ ラウンド目では人 $1$ と $2$、$3$ と $4$ がそれぞれ試合をし、前者の試合は人 $2$ が、後者の試合は人 $3$ が勝ちます。 $2$ ラウンド目では人 $2$ と $3$、$1$ と $4$ がそれぞれ試合をし、前者の試合は引き分け、後者の試合は人 $1$ が勝ちます。 よって最終的な順位は、上位から順に人 $1,2,3,4$ となります。