[APC001] C - Not APC

题目背景

这题并没有什么有趣的题目背景，祝您愉快。

题目描述

小 A 有一个**仅由 `A`、`P`、`C` 构成**的字符串 $S$。小 A 需要**尽可能地**不断在这个字符串中消除形如 `APC` 这样的**子序列**，直到无法消除。最后，小 A 需要输出消除后的字符串。如果字符串可以被消除成空串，则输出 `Perfect`。然而小 A 不会这个题，所以来找你帮忙。

输入输出格式

输入格式

第一行一个数 $T$ 表示数据组数。接下来 $T$ 行每行一个字符串 $S$.

输出格式

**本题使用 Special Judge。** 请输出最短的答案字符串，并给出一种删除的方案。对于每组数据，第一行输出一个最短的答案字符串。如果可能的最短答案字符串或生成最短答案字符串的方案有多种，请输出任意一个。接下来一行输出一个整数 $q$，表示你的删除次数。接下来 $q$ 行每行三个整数，分别表示你在一次操作中删除的字符 `A`、`P`、`C` **在原字符串中**的位置，**下标从 $1$ 开始**。

输入输出样例

输入样例 #1

5
PAAAAPPPCA
CAPPCPCAPAPA
PPAAAACCAAAAAAAAC
CAPPCAAPA
APPAACPPAPPPAPAAAA

输出样例 #1

PAAAPPA
1
5 6 9
CPPCAPAPA
1
2 4 5
PPAAAACCAAAAAAAAC
0
CPAAPA
1
2 3 5
PAAPPAPPPAPAAAA
1
1 2 6

输入样例 #2

1
APC

输出样例 #2

Perfect
1
1 2 3

输入样例 #3

10
PPCPAPAAACPAPACPPCPC
APPAPPAPPCPAPPCCCPPA
APPCCPPAPPAACCPPPPPP
PACPPCAPCPPCPPPAAAAC
PPPCPPCCPACAAACCCCAC
ACAAPCPAPAAAAPPACPPC
ACACPPCCPPAACPAAAAAC
APPCPCCCAPCACPAACACC
AACPCAPACPPPCAAPCCPC
PPACPPPCCAPAAAPCPAPA

输出样例 #3

PPCPAAPP
4
5 6 10
7 11 15
8 13 18
9 16 20
PPPPPPPA
4
1 2 10
4 5 15
7 8 16
12 13 17
PCPPPAACPPPPPP
2
1 2 4
8 9 13
PCPPPCPPPAAAAC
2
2 4 6
7 8 9
PPPCPPCCPACAAACCCCAC
0
CAAAAAPPAPP
3
1 5 6
3 7 17
4 9 20
CCPPACAAAAA
3
1 5 7
3 6 8
11 14 20
PPCCCCAAACC
3
1 2 4
9 10 11
12 14 17
CP
6
1 4 5
2 7 9
6 10 13
8 11 17
14 16 18
15 19 20
PPCPPCAAAPPAPA
2
3 5 8
10 11 16

说明

**样例解释 #1：** 对于第一组数据，字符串为 `PAAAAPPPCA`，下标为 $\{5,6,9\}$ 的字符串被删除，最终得到 `PAAAPPA`。对于第二组数据，字符串为 `CAPPCPCAPAPA`，下标为 $\{2,4,5\}$ 的字符被消除，得到 `CPPCAPAPA`。 **样例解释 #2：** 唯一的一组数据中，字符串为 `APC`，显然能被全部消除，方案也显然。 $1\leq T\leq 10$，$1\leq \sum |S|\leq 3\times 10^6$。