#include "hieroglyphs.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 200000
using namespace std;
const int inf=(int)(1e9);
vector<int>p[N+1];
vector<int>p2[N+1];
struct reads
{
	int num,data;
	bool operator < (const reads &t)const
	{
		return num<t.num;	
	}
};
reads tong[N+1],tong2[N+1];
int length,length2,leng,dque[N+1],dque2[N+1],pst,pst2,l[N+1],l2[N+1],r[N+1],r2[N+1],st[N+1],nt[N+1],nt2[N+1];
bool used[N+1],used2[N+1];
int get(int x,int d)
{
	return lower_bound(p[x].begin(),p[x].end(),d)-p[x].begin();
}
int get2(int x,int d)
{
	return lower_bound(p2[x].begin(),p2[x].end(),d)-p2[x].begin();
}
bool cmp(reads a,reads b)
{
	int d;
	if (get(a.data,nt[b.num])==get2(a.data,b.num)) d=nt[b.num];
	else d=nt2[b.num];
	return a.num<d;
}
std::vector<int> ucs(std::vector<int> A, std::vector<int> B)
{
	int ps=0,pst=-1,pst2=-1;
	bool op=0;
	vector<int>v;
	for (int i=0;i<A.size();++i) p[A[i]].push_back(i);
	for (int i=0;i<B.size();++i) p2[B[i]].push_back(i);
	for (int i=0;i<=N;++i)
	{
		if (p[i].size()<p2[i].size())
		{
			for (int j=0;j<p[i].size();++j) tong[++length]=(reads){p[i][j],i};
		}
		else
		{
			for (int j=0;j<p2[i].size();++j) tong2[++length2]=(reads){p2[i][j],i},nt[p2[i][j]]=p[i][j],nt2[p2[i][j]]=p[i][p[i].size()-p2[i].size()+j];
		}
	}
	sort(tong+1,tong+length+1),sort(tong2+1,tong2+length2+1);
	for (int i=1;i<=length2;++i)
	{
		while (ps+1<=length&&cmp(tong[ps+1],tong2[i])) st[++leng]=tong[++ps].data;
		st[++leng]=tong2[i].data;
	}
	for (int i=ps+1;i<=length;++i) st[++leng]=tong[i].data;
	for (int i=1;i<=leng;++i)
	{
		pst++,pst2++;
		while (pst<A.size()&&A[pst]!=st[i]) ++pst;
		while (pst2<B.size()&&B[pst2]!=st[i]) ++pst2;
		if (pst==A.size()||pst2==B.size()) return {-1};
		dque[i]=pst,dque2[i]=pst2,used[pst]=used2[pst2]=1,v.push_back(st[i]);
	}
	for (int i=0;i<=N;++i) l[i]=l2[i]=inf,r[i]=r2[i]=-inf;
	for (int i=0;i<A.size();++i)
		if (!used[i])
			l[A[i]]=min(l[A[i]],i),r[A[i]]=max(r[A[i]],i);
	for (int i=0;i<B.size();++i)
		if (!used2[i])
			l2[B[i]]=min(l2[B[i]],i),r2[B[i]]=max(r2[B[i]],i);
	for (int i=1;i<=leng;++i)
	{
		if (l[st[i]]<dque[i]) op=1;
		if (dque2[i]<r2[st[i]]&&op) return {-1};
	}
	op=0;
	for (int i=1;i<=leng;++i)
	{
		if (l2[st[i]]<dque2[i]) op=1;
		if (dque[i]<r[st[i]]&&op) return {-1};
	}
	for (int i=1;i<=leng;++i)
		for (int j=i+1;j<=leng;++j)
			if (r[st[i]]>dque[j]&&l2[st[j]]<dque2[i])
				return {-1};
	for (int i=1;i<=leng;++i)
		for (int j=i+1;j<=leng;++j)
			if (r2[st[i]]>dque2[j]&&l[st[j]]<dque[i])
				return {-1};
	return v;
}