P14448 [ICPC 2025 Xi'an R] Beautiful Dangos

小青鱼喜欢吃 **三色团子**！ :::align{center}  小青鱼 ::: 现在有 $n$ 个团子排成一串，每个团子的颜色可能是青色（$\texttt{C}$）、白色（$\texttt{W}$）或粉色（$\texttt{P}$）。这些团子的编号从 $1$ 到 $n$。 小青鱼认为一串团子是 **美丽的**，当且仅当任意相邻的两个团子颜色都不相同。 为了让这串三色团子更加美丽，小青鱼决定选择一个区间 $[l, r]$（$1 \leq l \leq r \leq n$），并将该区间内的所有团子随意重新排列，使得整个团子串在重新排列后变得美丽。 小青鱼希望他选择的这个区间尽可能短。你能帮帮他吗？你需要输出最优的区间，以及重新排列后的整串团子。 请注意，原本的团子串可能已经是美丽的，也可能无论怎样重新排列都无法变得美丽。

输入包含多个测试用例。第一行是一个整数 $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$。

对于每个测试用例： - 如果团子串已经是美丽的，输出一行 $\texttt{Beautiful}$。 - 否则，如果无论怎样重新排列都无法使团子串变得美丽，输出一行 $\texttt{Impossible}$。 - 否则，输出三行： - 第一行输出单词 $\texttt{Possible}$； - 第二行输出两个整数 $l$ 和 $r$，表示所选择的区间（$1 \leq l \leq r \leq n$）； - 第三行输出一个长度为 $n$ 的字符串，表示重新排列后的团子串。 如果存在多个符合条件的方案，你可以输出任意一个。

在第一个测试用例中，团子串已经是美丽的。 :::align{center}  ::: 在第二个测试用例中，最初的团子串并不美丽，因为第 3 个和第 4 个团子相邻且都是青色。但小青鱼可以选择区间 $[4, 5]$，并交换其中的两个团子，使整个团子串变得美丽。 :::align{center}  ::: 可以很容易地证明，这个方案所选的区间长度是最短的。 在第三个测试用例中，无论怎样重新排列，小青鱼都无法让团子串变得美丽。 翻译由 ChatGPT-5 完成