题目描述

Little Cyan Fish likes to eat $\textit{Tricolor Dango}$!

:::align{center}

$\textit{Little Cyan Fish}$ :::

Now there are $n$ dangos arranged in a string, and each dango is colored cyan ($\texttt{C}$), white ($\texttt{W}$), or pink ($\texttt{P}$). The dangos are numbered from $1$ to $n$.

Little Cyan Fish considers a string of dangos to be $\textit{beautiful}$ if and only if any two adjacent dangos have different colors.

To make this string of tricolor dango more beautiful, Little Cyan Fish decides to select an interval $[l, r]$ ($1 \leq l \leq r \leq n$), and rearrange all dangos in this interval arbitrarily, so that the entire string of dango becomes beautiful after the rearrangement.

Little Cyan Fish wants to make the interval he selects as short as possible. Can you help him? You need to output the optimal interval, as well as the whole string after rearrangement.

Note that the original string may already be beautiful, or it might be impossible to make it beautiful through any rearrangement.

输入格式

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. For each test case:

• The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^6$), which is the number of dangos in this string.
• The second line contains a string of length $n$, where the $i$-th character denotes the color of the $i$-th dango, with $\texttt{C}$ representing cyan, $\texttt{W}$ representing white, and $\texttt{P}$ representing pink.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^6$.

输出格式

For each test case:

• If the string of dangos is already beautiful, output a single line $\texttt{Beautiful}$.

• Otherwise, if it is impossible to make the string of dangos beautiful through any rearrangement, output a single line $\texttt{Impossible}$.

• Otherwise, output three lines:

  • The first line should contain the word $\texttt{Possible}$.
  • The second line should contain two integers $l$ and $r$, representing the selected interval ($1 \leq l \leq r \leq n$).
  • The third line should contain a string of length $n$, representing the colors of all dangos after rearrangement.

  If there are multiple possible solutions, you may output any of them.

4
5
CWCWC
6
CWCCPW
3
PPP
8
CWPPCWWC

Beautiful
Possible
4 5
CWCPCW
Impossible
Possible
4 6
CWPWCPWC

提示

In the first test case, the string of dangos is already beautiful.

:::align{center} :::

In the second test case, initially, the string of dangos is not beautiful because two adjacent dangos, the third and the fourth, are both cyan. But Little Cyan Fish can resolve this by selecting the interval $[4, 5]$ and swapping the two dangos within it.

:::align{center} :::

It can be easily shown that this solution selects an interval of the shortest possible length.

In the third test case, Little Cyan Fish can't make it beautiful through any rearrangement.