Score : $300$ points

问题描述

$2N$ 名玩家，编号为 $1$ 到 $2N$，将参加一场剪刀石头布比赛。

该比赛共有 $M$ 轮。每轮包含 $N$ 场一对一的比赛，每个玩家在其中参加一场比赛。

对于每个 $i=0, 1, \ldots, M$，在第 $i$ 轮结束后，玩家的排名确定方式如下：

• 在前 $i$ 轮中胜场更多的玩家排名更高。
• 若出现平局，则根据ID号码决定排名：ID号码较小的玩家排名更高。

另外，对于每个 $i=1, \ldots, M$，第 $i$ 轮的比赛安排如下：

• 对于每个 $k=1, 2, \ldots, N$，在第 $(i-1)$ 轮结束后排名第 $(2k-1)$ 和第 $2k$ 的两位玩家进行一场比赛。

在每场比赛中，两位玩家只进行一次比拼，结果是一方获胜、另一方失败，或者平局。

高桥能够预见未来，他知道玩家 $i$ 在第 $j$ 轮比赛中将出 $A_{i, j}$，其中 $A_{i,j}$ 表示 G、C 或 P。
这里，G 代表石头，C 代表剪刀，P 代表布。（这些符号源于日语）

请找出在第 $M$ 轮结束时所有玩家的排名。

剪刀石头布规则： 剪刀石头布比赛的结果基于两位玩家所出的手势按以下方式决定：

• 如果一位玩家出石头（G）而另一位出剪刀（C），则出石头（G）的玩家获胜。
• 如果一位玩家出剪刀（C）而另一位出布（P），则出剪刀（C）的玩家获胜。
• 如果一位玩家出布（P）而另一位出石头（G），则出布（P）的玩家获胜。
• 如果两位玩家出相同手势，则比赛为平局。

以上为通义千问 qwen-max 翻译，仅供参考。

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, or P.

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.

update @ 2024/3/10 09:46:53