题目描述

Qc 与 He 进行如下游戏。每一回合，He 在栅栏上写下字母 Q 或 C，新字母总是追加到当前字符串末尾；随后 Qc 可以交换两个已经写下的位置，也可以不进行操作。Qc 的第一次操作必须跳过。

Qc 的目标是：在他的每个奇数次操作之后，即第 $1,3,5,\ldots$ 次操作之后，栅栏上的字符串都是回文串。Qc 事先知道 He 将依次写出的完整字符串，请判断目标是否能够实现；若能，请输出任意一套操作方案。

输入格式

第一行包含整数 $n$，表示 He 总共会写下 $2n-1$ 个字母。

第二行包含长度为 $2n-1$ 的字符串，仅由 Q 和 C 组成。

输出格式

若 Qc 无法实现目标，输出一行 He。

否则第一行输出 Qc，随后输出 $2n-1$ 行。第 $i$ 行包含两个整数 $a_i,b_i$，表示 He 写下第 $i$ 个字母后 Qc 的操作：0 0 表示跳过，否则表示交换当前栅栏中位置 $a_i$ 与 $b_i$ 的字母。位置从 $1$ 开始编号。

若有多组方案，输出任意一组。

数据范围

• $1\le n\le2005$；
• 字符串长度恰为 $2n-1$。

样例 1

4
QCCQCQQ

Qc
0 0
0 0
1 2
3 4
3 4
0 0
1 4

样例 2

1
Q

Qc
0 0