#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
//#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
template<class S,class T>
bool chmin(S &a,const T &b) {
return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
return a<b?(a=b)==b:false;
}
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
const ll inf=1e18+7;
const ll mod=1e9+7;
const ll N=3e3+7;
const ld eps=1e-9;
ll dp[N][N][2];
str s1(ll n,vll a,vll b){
ll i,j;
memset(dp,0ll,sizeof(dp));
dp[1][0][0]=1;
dp[0][1][1]=1;
for(ll len=1;len<2*n;len++){
for(i=0;i<=len;i++){
j=len-i;
ll x=i+j-1;
if(i>n || j>n)continue;
if(i<n && a[x]<=a[x+1])dp[i+1][j][0]+=dp[i][j][0];
if(j<n && a[x]<=b[x+1])dp[i][j+1][1]+=dp[i][j][0];
if(i<n && b[x]<=a[x+1])dp[i+1][j][0]+=dp[i][j][1];
if(j<n && b[x]<=b[x+1])dp[i][j+1][1]+=dp[i][j][1];
}
}
if(!dp[n][n][0] && !dp[n][n][1]) { return "";}
ll A=n,B=n,c,x=n*2-1;
if(dp[n][n][0])c=0;
else c=1;
str ans;
while(x){
if(c==0){
ans+='A';
A--;
if(!A || a[x]<a[x-1] || !dp[A][B][0]) c=1;
x--;
}else{
ans+='B';
B--;
if(!B || b[x]<b[x-1] || !dp[A][B][1]) c=0;
x--;
}
}
if(A) ans+='A';
else ans+='B';
reverse(all(ans));
return ans;
}
bool s2(str ans,vll a,vll b){
ll i;
vll v,v2;
for(i=0;i<ans.sz;i++){
if(ans[i]=='A')v.pb(a[i]);
else v.pb(b[i]);
}
v2=v;
sort(all(v2));
if(v!=v2)return false;
return true;
}
signed main(){
ll i;
while(true){
ll n=rnd(1,5);
vll a(n*2),b(n*2);
for(auto &i : a) i=rnd(1,10);
for(auto &i : b) i=rnd(1,10);
if(!s2(s1(n,a,b),a,b)){
cout<<"Bad"<<endl;
cout<<n<<endl;
for(auto i : a) cout<<i<<' ';cout<<endl;
for(auto i : b) cout<<i<<' ';cout<<endl;
cout<<s1(n,a,b)<<endl;
return 0;
}
cout<<"Passed"<<endl;
}
return 0;
}
/*
*/
