#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;
int n,m,k,cnt;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int dp[MAXN][MAXN];
int nxt[MAXN][2*MAXN],last[2*MAXN];
unordered_map<int,int> mp;
int ret[200007];
double st,et;
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(rand()%2==0){
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);
}else{
if(a[l]==b[r] and dp[l][r]==dp[l-1][r-1]+1){
k++; c[k]=a[l];
findseq(l-1,r-1);
}
if(dp[l][r]==dp[l][r-1]){
findseq(l,r-1);
return;
}
if(dp[l][r]==dp[l-1][r]){
findseq(l-1,r);
return;
}
}
}
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 fuck;
bool brute(int x,int y,int z){
if(fuck)return false;
if(x==0 or y==0)return false;
//if(dp[x][y]<z*2/3)return false;
et=clock();
if((et-st)/CLOCKS_PER_SEC>0.95){
fuck=true; 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]]==0)res=true;
else if(brute(x-1,y-1,nxt[z][a[x]]))res=true;
}else{
if((x+y+z)%2==0){
if(brute(x-1,y,z))res=true;
else if(brute(x,y-1,z))res=true;
}else{
if(brute(x,y-1,z))res=true;
else if(brute(x-1,y,z))res=true;
}
}
return res;
}
vector<int> ucs(vector<int> A, vector<int> B){
st=clock();
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];
reverse(a+1,a+n+1);
reverse(b+1,b+m+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=k;i>=1;i--)d[k-i+1]=c[i];
reverse(a+1,a+n+1);
reverse(b+1,b+m+1);
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);
}
}
k=0;
findseq(n,m);
reverse(c+1,c+k+1);
for(int i=1;i<=k;i++){
if(c[i]!=d[i])return {-1};
}
for(int i=1;i<=cnt;i++)last[i]=0;
for(int i=1;i<=k+1;i++){
for(int f=1;f<=cnt;f++)nxt[i][f]=last[f];
last[c[i]]=i;
}
vector<int> sol;
if(!brute(n,m,k+1)){
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;
}*/
