题目描述

$2N$名选手，编号从1到$2N$，将参加一场石头剪刀布比赛。比赛共有$M$轮。每轮有$N$场一对一的比赛，每名选手参加其中一场。对于每个$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。这里，G代表石头，C代表剪刀，P代表布。

剪刀石头布的规则如下：

• 如果一方出剪刀（C），另一方出布（P），则出剪刀的一方获胜。
• 如果一方出布（P），另一方出石头（G），则出布的一方获胜。
• 如果一方出石头（G），另一方出剪刀（C），则出石头的一方获胜。
• 如果双方出同样的手势，则为平局。

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

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$

$A_{1,1}$ $A_{1,2}...A_{1,M}$

$A_{2,1}$ $A_{2,2}...A_{2,M}$

$\vdots$

$A_{2N,1}$ $A_{2N,2}...A_{2N,M}$

输出格式

输出$2N$行。第$i$行应包含第$M$轮结束时排名第$i$的选手的ID号。

样例

2 3
GCP
PPP
CCC
PPC

3
1
2
4

2 2
GC
PG
CG
PP

1
2
3
4

样例解释

【样例1说明】
第一轮，选手1和2比赛，选手3和4比赛。选手2赢了前者，选手3赢了后者。
第二轮，选手2和3比赛，选手1和4比赛。选手3赢了前者，选手1赢了后者。
第三轮，选手3和1比赛，选手2和4比赛。选手3赢了前者，选手4赢了后者。
因此，最后选手的排名顺序是：3,1,2,4，从高到低。
【样例2说明】
第一轮，选手1和2比赛，选手3和4比赛。选手2赢了前者，选手3赢了后者。
第二轮，选手2和3比赛，选手1和4比赛。前者平局，选手1赢了后者。
因此，最后选手的排名顺序是：1,2,3,4，从高到低。

数据范围

• $1 \leq N \leq 50$
• $1 \leq M \leq 100$
• $A_{i,j}$是G、C或P。

来源

• AtCoder ABC222C