考虑只有三个字符，所以每四个必然选出两个来，也就是不存在\(\rm impossible\)的情况

所以我们简单模拟就好了，从两端往中间扫，不匹配就移动一端，时间复杂度\(O(n)\)。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define rg registervoid read(int &x){    char ch;bool ok;    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=1e6+10;char a[maxn],ans[maxn];int n,m,mx,sum;int pos[maxn],tot,w[3],s[3];int main(){    scanf("%s",a+1),n=strlen(a+1);m=n/2;    if(n==2)return printf("%c",a[1]),0;    int l=1,r=n;    while(l