#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#define sz(x) int32_t(x.size())
#define all(x) x.begin(),x.end()
const int N = 1e5+5, V = 2e5+5;
vector<int> idsa[V], idsb[V], idd[V], va, vb;
int n, m, cnt[V], frq_habd[V], bit[N];
bool AA[V], BB[V];
void upd(int i, int v) {
++i;
while (i <= m) {
bit[i] = max(bit[i], v);
i += (i & -i);
}
}
int get(int i) {
++i;
int ret = 0;
while (i) {
ret = max(ret, bit[i]);
i -= (i & -i);
}
return ret;
}
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);
int mx_frq = 0;
for (int i = 0; i < n; i++) {
idsa[A[i]].push_back(i);
frq_habd[A[i]]++;
}
for (int i = 0; i < m; i++) {
idsb[B[i]].push_back(i);
mx_frq = max(mx_frq, ++frq_habd[B[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);
return ret;
} else if (fri) {
ret.push_back(A[va[i++]]);
cnt[ret.back()]++;
} else {
ret.push_back(B[vb[j++]]);
cnt[ret.back()]++;
}
}
j = 0;
for (int i = 0; i < n && j < sz(ret); i++) {
if (A[i] == ret[j]) {
j++;
}
}
if (j < sz(ret)) {
ret.clear();
ret.push_back(-1);
return ret;
}
j = 0;
for (int i = 0; i < m && j < sz(ret); i++) {
if (B[i] == ret[j]) {
j++;
}
}
if (j < sz(ret)) {
ret.clear();
ret.push_back(-1);
return ret;
}
if (max(n, m) <= 3000 || mx_frq <= 5) {
for (int i = 0; i < sz(ret); i++) {
idd[ret[i]].push_back(i);
}
for (int i = 0; i < V; i++) {
reverse(all(idsb[i]));
}
for (int i = 0; i < n; i++) {
for (auto &j : idsb[A[i]]) {
int habd = get(j - 1);
int bruh = lower_bound(all(idd[A[i]]), habd) - idd[A[i]].begin();
if (bruh == sz(idd[A[i]])) {
ret.clear();
ret.push_back(-1);
return ret;
}
upd(j, idd[A[i]][bruh] + 1);
}
}
}
return ret;
}
