#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;
int n,m,k,cnt;
int a[MAXN],b[MAXN],c[MAXN];
int dp[MAXN][MAXN];
int nxt[MAXN][2*MAXN],last[2*MAXN];
unordered_map<int,int> mp;
int ret[200007];
void compress(){
vector<int> vals;
for(int i=1;i<=n;i++)vals.push_back(a[i]);
for(int i=1;i<=m;i++)vals.push_back(b[i]);
sort(vals.begin(),vals.end());
cnt=0;
for(int i=0;i<vals.size();i++){
if(i==0 or vals[i]!=vals[i-1])cnt++;
mp[vals[i]]=cnt; ret[cnt]=vals[i];
}
for(int i=1;i<=n;i++)a[i]=mp[a[i]];
for(int i=1;i<=m;i++)b[i]=mp[b[i]];
}
void findseq(int l,int r){
if(dp[l][r]==0)return;
if(dp[l][r]==dp[l-1][r]){
findseq(l-1,r);
return;
}
if(dp[l][r]==dp[l][r-1]){
findseq(l,r-1);
return;
}
k++; c[k]=a[l];
findseq(l-1,r-1);
}
unordered_set<long long> s;
long long state(long long a,long long b,long long c){
return c+b*10000+a*10000*10000;
}
bool brute(int x,int y,int z){
if(x==n+1 or y==n+1)return false;
long long curr=state(x,y,z);
if(s.find(curr)!=s.end())return false;
s.insert(curr);
bool res=false;
if(a[x]==b[y]){
if(nxt[z][a[x]]>k)res=true;
else if(brute(x+1,y+1,nxt[z][a[x]]))res=true;
}else{
if(brute(x+1,y,z))res=true;
else if(brute(x,y+1,z))res=true;
}
return res;
}
vector<int> ucs(vector<int> A, vector<int> B){
n=int(A.size());
m=int(B.size());
for(int i=1;i<=n;i++)a[i]=A[i-1];
for(int i=1;i<=m;i++)b[i]=B[i-1];
compress();
for(int i=1;i<=n;i++){
for(int f=1;f<=m;f++){
dp[i][f]=max(dp[i-1][f],dp[i][f-1]);
if(a[i]==b[f])dp[i][f]=max(dp[i][f],dp[i-1][f-1]+1);
}
}
findseq(n,m);
reverse(c+1,c+k+1);
for(int i=1;i<=cnt;i++)last[i]=k+1;
for(int i=k;i>=0;i--){
for(int f=1;f<=cnt;f++)nxt[i][f]=last[f];
last[c[i]]=i;
}
vector<int> sol;
if(!brute(1,1,0)){
for(int i=1;i<=k;i++)sol.push_back(ret[c[i]]);
return sol;
}
return {-1};
}
/*int main(){
//auto s=ucs({0, 0, 1, 0, 1, 2}, {2, 0, 1, 0, 2});
auto s=ucs({0, 1, 0}, {1, 0, 1});
for(int i:s)cout<<i<<" ";
return 0;
}*/
