题目描述

$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$ 位である人の番号を出力せよ。

题目大意

有 $2n$ 个人玩剪刀石头布。

告诉你每一轮出的手势，然后执行 $m$ 次下面的操作：

• 首先，$2i$ 和 $2i-1$ 两个人进行比赛。
• 然后按照胜利的场数第一关键字，编号第二关键字进行排序。

游戏规则：

• 如果两个人出的手势相同那么平局。
• 否则，$G$ 可以赢 $C$，$C$ 可以赢 $P$，$P$ 可以赢 $G$。

最后问第 $i$ 名是几号。

$1\le n\le 50$，$1\le m\le 100$。

2 3
GCP
PPP
CCC
PPC

3
1
2
4

2 2
GC
PG
CG
PP

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