#include "hieroglyphs.h"
#include <bits/stdc++.h>
std::vector<int> A,B;
int vi2[200009],vi1[200009],dp[3009][3009],la[200009],l1[200009],
l2[200009],N,M,vq[200009];
bool vl1(int l,int r,int x) {
	memset(vq,0,sizeof(vq));
	for(int i=x+1;i<N;i++) {
		vq[A[i]]|=1;
	}
	for(int i=r+1;i<M;i++) {
		vq[B[i]]|=2;
	}
	for(int i=l+1;i<r;i++) {
		if(vq[B[i]]==1) {
			return 0;
		}
	}
	return 1;
}
bool vl2(int l,int r,int x) {
	memset(vq,0,sizeof(vq));
	for(int i=x+1;i<M;i++) {
		vq[B[i]]|=1;
	}
	for(int i=r+1;i<N;i++) {
		vq[A[i]]|=2;
	}
	for(int i=l+1;i<r;i++) {
		if(vq[A[i]]==1) {
			return 0;
		}
	}
	return 1;
}
std::vector<int> ucs(std::vector<int> AA, std::vector<int> BB) {
	A=AA;B=BB;
	N=A.size(),M=B.size();
	memset(vi2,0,sizeof(vi2));
	memset(vi1,0,sizeof(vi1));
	std::vector<int> wj;wj.push_back(-1);
	for(int i=M-1;i>=0;i--) {
		vi2[B[i]]++;
	}
	for(int i=N-1;i>=0;i--) {
		vi1[A[i]]++;
	}
	for(int i=0;i<=200000;i++) {
		if(vi1[i]==vi2[i]) vi1[i]=vi2[i]=1;
		else if(vi1[i]<=vi2[i]) vi2[i]=0;
		else vi1[i]=0;
 	}
 	dp[0][0]=1;
 	for(int i=0;i<=N;i++) {
 		for(int j=0;j<=M;j++) {
 			if(i&&j&&A[i-1]==B[j-1]) {
 				dp[i][j]|=dp[i-1][j-1];
 			}
 			if(i&&vi1[A[i-1]]==0) dp[i][j]|=dp[i-1][j];
 			if(j&&vi2[B[j-1]]==0) dp[i][j]|=dp[i][j-1];
 		}
 	}
 	if(!dp[N][M]) {
 		return wj;
 	}
	std::vector<int> tp,tp2;
	int x=N,y=M;
	while(x||y) {
		if(x&&vi1[A[x-1]]==0&&dp[x-1][y]) {
			x--;
		} else if(y&&vi2[B[y-1]]==0&&dp[x][y-1]){
			y--;
		} else {
			tp.push_back(x-1);
			tp2.push_back(y-1);
			x--;y--;			
		}
	}
	std::reverse(tp.begin(),tp.end());
	std::reverse(tp2.begin(),tp2.end());
	memset(vi1,0,sizeof(vi1));
	memset(vi2,0,sizeof(vi2));
	for(int i=0;i<tp.size();i++) vi1[tp[i]]=1;
	for(int i=0;i<tp.size();i++) vi2[tp2[i]]=1;
	memset(la,-1,sizeof(la));
	for(int i=0;i<N;i++) {
		l1[i]=la[A[i]];
		la[A[i]]=i;
	}
	memset(la,-1,sizeof(la));
	for(int i=0;i<M;i++) {
		l2[i]=la[B[i]];
		la[B[i]]=i;
	}
	for(int i=0;i<tp.size();i++) {
		int x=l2[tp2[i]];
		if(x==-1||vi2[x]) continue;
		if(!vl1(x,tp2[i],tp[i])) return wj;
	}
	for(int i=0;i<tp2.size();i++) {
		int x=l1[tp[i]];
		if(x==-1||vi1[x]) continue;
		if(!vl2(x,tp[i],tp2[i])) return wj;
	}
	for(int i=0;i<tp.size();i++) tp[i]=A[tp[i]];
	return tp;
}