#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#define sz(x) int32_t(x.size())
const int N = 1e5+5, V = 2e5+5;
vector<int> idsa[V], idsb[V], va, vb;
int n, m, cnt[V];
bool AA[V], BB[V];
bool oki(int val, int frq, int val2, int frq2) {
int i = idsa[val][frq-1];
int j = idsb[val][frq-1];
int i2 = idsa[val2][sz(idsa[val2])-frq2];
int j2 = idsb[val2][sz(idsb[val2])-frq2];
return (i < i2 && j < j2);
}
std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
vector<int> ret;
n = sz(A), m = sz(B);
for (int i = 0; i < n; i++) {
idsa[A[i]].push_back(i);
}
for (int i = 0; i < m; i++) {
idsb[B[i]].push_back(i);
}
for (int i = 0; i < V; i++) {
if (idsa[i].empty() && idsb[i].empty())continue;
if (sz(idsa[i]) <= sz(idsb[i])) {
AA[i] = true;
} else {
BB[i] = true;
}
}
for (int i = 0; i < n; i++) {
if (AA[A[i]]) {
va.push_back(i);
}
}
for (int i = 0; i < m; i++) {
if (BB[B[i]]) {
vb.push_back(i);
}
}
int i = 0, j = 0;
while (i < sz(va) || j < sz(vb)) {
if (j == sz(vb)) {
ret.push_back(A[va[i++]]);
cnt[ret.back()]++;
continue;
}
if (i == sz(va)) {
ret.push_back(B[vb[j++]]);
continue;
}
bool fri = false, frj = false;
int val1 = A[va[i]], val2 = B[vb[j]];
if (oki(val1, 1 + cnt[val1], val2, sz(idsb[val2]) - cnt[val2])) {
fri = true;
}
if (oki(val2, 1 + cnt[val2], val1, sz(idsa[val1]) - cnt[val1])) {
frj = true;
}
if (fri && frj) {
ret.clear();
ret.push_back(-1);
break;
} else if (fri) {
ret.push_back(A[va[i++]]);
cnt[ret.back()]++;
} else {
ret.push_back(B[vb[j++]]);
cnt[ret.back()]++;
}
}
return ret;
}
