#include <bits/stdc++.h>
#include "hieroglyphs.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 300 * 1000 + 7;
int tab[N][2], nxt[N][2], rev[N];
map<int, int> scl;
vector<int> pos[N][2];
set<int>::iterator it;
int Il(int a, int i, int r)
{
//cout << "Il: " << a << " " << i << " " << r << " " << (pos[a][r].size()) << "\n";
return (pos[a][r].end() - lower_bound(pos[a][r].begin(), pos[a][r].end(), i));
}
int Nxt(int a, int i, int r)
{
int j = (upper_bound(pos[a][r].begin(), pos[a][r].end(), i) - pos[a][r].begin());
if(j == (int)pos[a][r].size())
return N - 3;
return pos[a][r][j];
}
void Scl(int n, int m)
{
vector<int> v;
for(int i = 1; i <= n; ++i)
v.pb(tab[i][0]);
for(int i = 1; i <= m; ++i)
v.pb(tab[i][1]);
sort(v.begin(), v.end());
int l = -1;
for(int i = 0; i < (int)v.size(); ++i)
{
if(i == 0 || v[i] != v[i - 1]) ++l;
scl[v[i]] = l; rev[l] = v[i];
}
for(int i = 1; i <= n; ++i)
{
tab[i][0] = scl[tab[i][0]];
pos[tab[i][0]][0].pb(i);
}
for(int i = 1; i <= m; ++i)
{
tab[i][1] = scl[tab[i][1]];
pos[tab[i][1]][1].pb(i);
}
}
void Gen(int n, int m)
{
nxt[n + 1][0] = n + 1;
nxt[m + 1][1] = m + 1;
for(int i = n; i >= 1; --i)
{
nxt[i][0] = nxt[i + 1][0];
if((int)pos[tab[i][0]][0].size() <= (int)pos[tab[i][0]][1].size())
nxt[i][0] = i;
}
for(int i = m; i >= 1; --i)
{
nxt[i][1] = nxt[i + 1][1];
if((int)pos[tab[i][1]][1].size() <= (int)pos[tab[i][1]][0].size())
nxt[i][1] = i;
}
nxt[0][0] = nxt[1][0];
nxt[0][1] = nxt[1][1];
}
vector<int> ucs(vector<int> A, vector<int> B)
{
int n = A.size(), m = B.size();
vector<int> answer, fans = {-1};
for(int i = 0; i < n; ++i)
tab[i + 1][0] = A[i];
for(int i = 0; i < m; ++i)
tab[i + 1][1] = B[i];
Scl(n, m);
Gen(n, m);
tab[n + 1][0] = N - 6; tab[m + 1][1] = N - 5;
int i = 0, j = 0;
while(i < n && j < m)
{
int a = tab[nxt[i + 1][0]][0], b = tab[nxt[j + 1][1]][1];
if(nxt[i + 1][0] > n && nxt[j + 1][1] > m) break;
if(a == b)
{
answer.pb(rev[a]);
i = nxt[i + 1][0]; j = nxt[j + 1][1];
continue;
}
int il1 = Il(a, i + 1, 0), il2 = Il(b, j + 1, 1);
//int n1 = Nxt(a, 1, nxt[j + 1][1]), n2 = Nxt(b, 0, nxt[i + 1][0]);
bool cz1 = (Nxt(a, j, 1) < nxt[j + 1][1] && Il(b, nxt[i + 1][0], 0) >= il2);
bool cz2 = (Nxt(b, i, 0) < nxt[i + 1][0] && Il(a, nxt[j + 1][1], 1) >= il1);
//cout << a << " " << b << "\n";
//cout << i << " " << j << " " << nxt[i + 1][0] << " " << nxt[j + 1][1] << "\n";
//cout << Il(b, nxt[i + 1][0], 0) << " " << Il(a, nxt[j + 1][1], 1) << "\n";
//cout << il1 << " " << il2 << "\n";
//cout << cz1 << " " << cz2 << "\n";
if(!(cz1 ^ cz2))
return fans;
if(cz1)
{
i = nxt[i + 1][0];
j = Nxt(a, j, 1);
}else
{
i = Nxt(b, i, 0);
j = nxt[j + 1][1];
}
answer.pb(rev[tab[i][0]]);
}
int anss = 0;
for(int i = 0; i <= n + m; ++i)
anss += (int)min(pos[i][0].size(), pos[i][1].size());
if(anss != (int)answer.size())
return fans;
return answer;
}
