Description

小青鱼喜欢吃 三色团子！

:::align{center}

小青鱼 :::

现在有 $n$ 个团子排成一串，每个团子的颜色可能是青色（$\texttt{C}$）、白色（$\texttt{W}$）或粉色（$\texttt{P}$）。这些团子的编号从 $1$ 到 $n$。

小青鱼认为一串团子是 美丽的，当且仅当任意相邻的两个团子颜色都不相同。

为了让这串三色团子更加美丽，小青鱼决定选择一个区间 $[l, r]$（$1 \leq l \leq r \leq n$），并将该区间内的所有团子随意重新排列，使得整个团子串在重新排列后变得美丽。

小青鱼希望他选择的这个区间尽可能短。你能帮帮他吗？你需要输出最优的区间，以及重新排列后的整串团子。

请注意，原本的团子串可能已经是美丽的，也可能无论怎样重新排列都无法变得美丽。

Input Format

输入包含多个测试用例。第一行是一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^6$），表示团子串的长度。
• 第二行包含一个长度为 $n$ 的字符串，其中第 $i$ 个字符表示第 $i$ 个团子的颜色。字符 $\texttt{C}$ 表示青色，$\texttt{W}$ 表示白色，$\texttt{P}$ 表示粉色。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^6$。

Output Format

对于每个测试用例：

• 如果团子串已经是美丽的，输出一行 $\texttt{Beautiful}$。
• 否则，如果无论怎样重新排列都无法使团子串变得美丽，输出一行 $\texttt{Impossible}$。
• 否则，输出三行：
• 第一行输出单词 $\texttt{Possible}$；
• 第二行输出两个整数 $l$ 和 $r$，表示所选择的区间（$1 \leq l \leq r \leq n$）；
• 第三行输出一个长度为 $n$ 的字符串，表示重新排列后的团子串。

如果存在多个符合条件的方案，你可以输出任意一个。

4
5
CWCWC
6
CWCCPW
3
PPP
8
CWPPCWWC

Beautiful
Possible
4 5
CWCPCW
Impossible
Possible
4 6
CWPWCPWC

Hint

在第一个测试用例中，团子串已经是美丽的。

:::align{center} :::

在第二个测试用例中，最初的团子串并不美丽，因为第 3 个和第 4 个团子相邻且都是青色。但小青鱼可以选择区间 $[4, 5]$，并交换其中的两个团子，使整个团子串变得美丽。

:::align{center} :::

可以很容易地证明，这个方案所选的区间长度是最短的。

在第三个测试用例中，无论怎样重新排列，小青鱼都无法让团子串变得美丽。

翻译由 ChatGPT-5 完成