Swiss-System Tournament

题目描述

有 $2N$ 个人，编号为 $1$ 到 $2N$，进行一次“猜拳”大会。

大会共进行 $M$ 轮，每一轮包含 $N$ 场 $1$ 对 $1$ 的比赛，每个人每轮只参加一次比赛。

对于 $i=0,1,\ldots,M$，第 $i$ 轮结束时的排名规则如下：

• 到第 $i$ 轮为止，胜场数多的人排名更高；
• 若胜场数相同，编号较小的人排名更高。

对于 $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 之一，分别表示石头、剪刀、布。

请你求出第 $M$ 轮结束时的最终排名。

猜拳规则如下：

• 一方出石头，另一方出剪刀，则出石头者胜，出剪刀者负；
• 一方出剪刀，另一方出布，则出剪刀者胜，出布者负；
• 一方出布，另一方出石头，则出布者胜，出石头者负；
• 双方出相同手势，则为平局。

输入格式

输入通过标准输入给出，格式如下：

$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 之一

样例解释 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$。

样例解释 2

第 $1$ 轮中，$1$ 号与 $2$ 号、$3$ 号与 $4$ 号分别比赛，前一场 $2$ 号胜，后一场 $3$ 号胜。
第 $2$ 轮中，$2$ 号与 $3$ 号、$1$ 号与 $4$ 号分别比赛，前一场平局，后一场 $1$ 号胜。
因此最终排名依次为 $1,2,3,4$。