//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> ucs(vector<int> A,vector<int> B)
{
	int la=sz(A);
	int lb=sz(B);
	const int m=2e5+10;
	vector<int> ca(m),cb(m);
	for(auto x:A) ca[x]++;
	for(auto x:B) cb[x]++;
	vector<int> major(m);
	for(int i=0;i<m;i++)
		major[i]=ca[i]>=cb[i];
	vector<int> sa,sb;
	for(int i=0;i<la;i++)
		if(!major[A[i]])
			sa.pb(i);
	for(int i=0;i<lb;i++)
		if(major[B[i]])
			sb.pb(i);
	int p1=0,p2=0;
	vector<int> U;
	vector<vector<int>> posa(m),posb(m);
	for(int i=0;i<la;i++)
		posa[A[i]].pb(i);
	for(int i=0;i<lb;i++)
		posb[B[i]].pb(i);
	int cura=0,curb=0;
	while(p1<sz(sa)&&p2<sz(sb))
	{
		int u=sa[p1];
		int v=sb[p2];
		int q1=lb(posa[B[v]],cura);
		int q2=lb(posb[A[u]],curb);
		if(q1==sz(posa[B[v]])||q2==sz(posb[A[u]])) return {-2};
		int u2=posa[B[v]][q1];
		int v2=posb[A[u]][q2];
		if(u2>u&&v2>v) return {-1};
		if(u2>u)
		{
			U.pb(A[u]);
			p1++;
			cura=u;
		}
		else if(v2>v)
		{
			U.pb(B[v]);
			p2++;
			curb=v;
		}
		else
		{
			int qa=lb(posa[B[v]],u);
			int cnta=sz(posa[B[v]])-qa;
			int qb=lb(posb[B[v]],v);
			int cntb=sz(posb[B[v]])-qb;
			if(cnta>=cntb)
			{
				U.pb(A[u]);
				p1++;
				cura=u;
			}
			else
			{
				U.pb(B[v]);
				p2++;
				curb=v;
			}
		}
	}
	while(p1<sz(sa)) U.pb(A[sa[p1++]]);
	while(p2<sz(sb)) U.pb(B[sb[p2++]]);
	return U;
}