[ABC222C] Swiss-System Tournament

题面翻译

2N名选手，编号从1到N，将参加一场石头剪刀布比赛。

比赛共有M轮，每轮有场一对一的比赛，每名选手参加其中一场。

对于每个$i=1,2,3...m$，第i轮结束时选手的排名按以下方式确定：

• 在前i轮中获胜次数多的选手排名更高。
• 平局时，编号小的选手排名更高。

此外，对于每个$i=1,2,3...M$，第i轮的比赛安排如下：

• 对于每个$k=1,2,3...N$，第i-1轮结束时排名第2k和第2k-1的选手进行一场比赛。

  在每场比赛中，两名选手只出一次手，结果是一方胜一方负，或平局。

  小高能预见未来，知道选手i 在第 j 轮的比赛中会出$A_{i,j}$，其中$A_{i,j}$是G、C或P。

  这里，G代表石头，C代表剪刀，P代表布。

  请找出第M轮结束时选手的排名。

题目描述

$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$ 人の出した手に応じて次のように決まります。 - 一方がグーで他方がチョキのとき、グーを出した人が勝ち、チョキを出した人は負け

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

输入格式

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

$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

样例输入 #1

2 3
GCP
PPP
CCC
PPC

样例输出 #1

3
1
2
4

样例 #2

样例输入 #2

2 2
GC
PG
CG
PP

样例输出 #2

1
2
3
4

提示

制約

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

Sample Explanation 1

$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$ となります。

Sample Explanation 2

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