/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 ラウンド目終了時点の順位を求めてください。
じゃんけんのルール
じゃんけんの結果は、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 となります。
Score : 300 points
Problem Statement
2N players, with ID numbers 1 through 2N, will participate in a rock-scissors-paper contest.
The contest has M rounds. Each round has N one-on-one matches, where each player plays in one of them.
For each i=0, 1, \ldots, M, the players' ranks at the end of the i-th round are determined as follows.
- A player with more wins in the first i rounds ranks higher.
- Ties are broken by ID numbers: a player with a smaller ID number ranks higher.
Additionally, for each i=1, \ldots, M, the matches in the i-th round are arranged as follows.
- For each k=1, 2, \ldots, N, a match is played between the players who rank (2k-1)-th and 2k-th at the end of the (i-1)-th round.
In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.
Takahashi, who can foresee the future, knows that Player i will play A_{i, j} in their match in the j-th round, where A_{i,j} is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)
Find the players' ranks at the end of the M-th round.
Rules of rock-scissors-paper
The result of a rock-scissors-paper match is determined as follows, based on the hands played by the two players.- If one player plays rock (G) and the other plays scissors (C), the player playing rock (G) wins.
- If one player plays scissors (C) and the other plays paper (P), the player playing scissors (C) wins.
- If one player plays paper (P) and the other plays rock (G), the player playing paper (P) wins.
- If the players play the same hand, the match is drawn.
Constraints
- 1 \leq N \leq 50
- 1 \leq M \leq 100
- A_{i,j} is
G,C, orP.
Input
Input is given from Standard Input in the following format:
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}
Output
Print 2N lines.
The i-th line should contain the ID number of the player who ranks i-th at the end of the M-th round.
Sample Input 1
2 3 GCP PPP CCC PPC
Sample Output 1
3 1 2 4
In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. Player 3 wins the former, and Player 1 wins the latter.
In the third round, matches are played between Players 3 and 1, and between Players 2 and 4. Player 3 wins the former, and Player 4 wins the latter.
Therefore, in the end, the players are ranked in the following order: 3,1,2,4, from highest to lowest.
Sample Input 2
2 2 GC PG CG PP
Sample Output 2
1 2 3 4
In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. The former is drawn, and Player 1 wins the latter.
Therefore, in the end, the players are ranked in the following order: 1,2,3,4, from highest to lowest.