P11138 [APC001] C - Not APC

This problem does not have any interesting background. Have fun.

Player A has a string $S$ **made up only of** `A`, `P`, and `C`. Player A needs to **eliminate as many as possible** subsequences of the form `APC` from this string repeatedly, until no more eliminations can be done. Finally, Player A needs to output the string after all eliminations. If the string can be eliminated into the empty string, output `Perfect`. However, Player A cannot solve this problem, so they ask you for help.

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain a string $S$.

**This problem uses Special Judge.** Please output the shortest possible resulting string, and provide one deletion plan. For each test case, output the following: On the first line, output one shortest possible resulting string. If there are multiple shortest possible resulting strings or multiple plans to obtain a shortest resulting string, output any one of them. On the next line, output an integer $q$, the number of deletions you perform. On the next $q$ lines, output three integers each, representing the positions **in the original string** of the deleted characters `A`, `P`, and `C` in one operation. **Indices start from $1$.**

**Sample Explanation #1:** For the first test case, the string is `PAAAAPPPCA`. Deleting the characters at indices $\{5,6,9\}$ results in `PAAAPPA`. For the second test case, the string is `CAPPCPCAPAPA`. Eliminating the characters at indices $\{2,4,5\}$ results in `CPPCAPAPA`. **Sample Explanation #2:** In the only test case, the string is `APC`. Clearly, it can be completely eliminated, and the plan is also obvious. $1\leq T\leq 10$, $1\leq \sum |S|\leq 3\times 10^6$. Translated by ChatGPT 5