#P18046. Beautiful Dangos

Beautiful Dangos

Beautiful Dangos

给定长度为 nn 的字符串 ss,每个字符都是 C、W、P 之一。若任意两个相邻字符都不同,则称这个字符串是美丽的。

你可以选择一个非空连续区间 [l,r][l,r],将这个区间内的字符任意重新排列,区间外的字符保持不变。请让整个字符串变得美丽,并使所选区间的长度 r−l+1r-l+1 最小。你需要输出最短区间和重排后的完整字符串。

若原字符串已经美丽,或者不存在任何可行重排,则按下方要求报告。

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例包含两行:第一行一个整数 nn,第二行是字符串 ss。

输出格式

对每个测试用例:

  • 若原字符串已经美丽,仅输出一行 Beautiful。
  • 否则,若无论怎样重排都不可能变美丽,仅输出一行 Impossible。
  • 否则输出三行:第一行 Possible;第二行两个整数 l,rl,r;第三行重排后的长度为 nn 的完整字符串。

区间必须是最短可行区间。如果最优方案不唯一,输出任意一种。只要求方案合法并达到最短长度,不要求与标准输出的区间或字符串完全相同。

数据范围

1≤t≤1051\le t\le10^5,1≤n≤2×1061\le n\le2\times10^6。一个输入文件中所有测试用例的 nn 之和不超过 2×1062\times10^6。

样例 1

输入:

4
5
CWCWC
6
CWCCPW
3
PPP
8
CWPPCWWC

输出:

Beautiful
Possible
4 5
CWCPCW
Impossible
Possible
4 6
CWPWCPWC