提交链接

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+10;
int T;
string s;
int numa,nump,numc;
int a[N],p[N],c[N];
struct node{
	int a,b,c;
}out[N];
void solve(){
	cin>>s;
	numa=nump=numc=0;
	memset(out,0,sizeof(out));
	memset(a,0,sizeof(a));
	memset(p,0,sizeof(p));
	memset(c,0,sizeof(c));
	int l=s.size();
	s=' '+s;
	for(int i=1;i<=l;i++){
		if(s[i]=='A')a[++numa]=i;
		else if(s[i]=='P')p[++nump]=i;
		else c[++numc]=i;
	}
	sort(a+1,a+numa+1);
	sort(p+1,p+nump+1);
	sort(c+1,c+numc+1);
	int ans=0;
	for(int i=1;i<=numa;i++){
		int t1=upper_bound(p+1,p+nump+1,a[i])-p;
		if(t1>=nump+1){
			break;
		} 
		int t2=upper_bound(c+1,c+numc+1,p[t1])-c;
		if(t2>=numc+1){
			break;
		} 
		s[a[i]]='M';
		s[p[t1]]='M';
		s[c[t2]]='M';
		out[++ans].a=a[i];
		out[ans].b=p[t1];
		out[ans].c=c[t2];
		a[i]=-1;p[t1]=-1;c[t2]=-1;	
	}
	if(ans==0){
		cout<<"0\n";
		return;
	}
	int num=0;
	for(int i=1;i<=l;i++){
		if(s[i]=='M')continue;
		cout<<s[i];
		num++;
	}
	if(num==0)cout<<"Perfect";
	cout<<"\n"<<ans<<"\n";
	for(int i=1;i<=ans;i++){
		cout<<out[i].a<<" "<<out[i].b<<" "<<out[i].c<<"\n";
	}
}
signed main(){
	cin>>T;
	while(T--)solve();
	return 0;
}