問題文

$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$ ラウンド目終了時点の順位を求めてください。

じゃんけんのルール じゃんけんの結果は、$2$ 人の出した手に応じて次のように決まります。

• 一方がグーで他方がチョキのとき、グーを出した人が勝ち、チョキを出した人は負け
• 一方がチョキで他方がパーのとき、チョキを出した人が勝ち、パーを出した人は負け
• 一方がパーで他方がグーのとき、パーを出した人が勝ち、グーを出した人は負け
• 両者が同じ手を出したとき、引き分け

制約

• $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$ 位である人の番号を出力せよ。

入力例 1

2 3
GCP
PPP
CCC
PPC

出力例 1

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 2
GC
PG
CG
PP

出力例 2

1
2
3
4

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