#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
constexpr ll inf = 4e18;
mt19937 mt(time(0));
struct segtree {
ll nt = 0;
vector<ll> tree;
segtree(ll n) {
nt = 1;
while (nt < n) nt *= 2;
tree = vector<ll>(2*nt, inf);
}
void point_set(ll i, ll v) { return point_set(1, 0, nt-1, i, v); }
void point_set(ll k, ll tl, ll tr, ll i, ll v) {
if (tl == tr) return tree[k] = v, void();
ll mid = tl + (tr - tl) / 2;
if (i <= mid) point_set(2*k, tl, mid, i, v);
else point_set(2*k+1, mid+1, tr, i, v);
tree[k] = min(tree[2*k], tree[2*k+1]);
}
ll range_min(ll l, ll r) { return range_min(1, 0, nt-1, l, r); }
ll range_min(ll k, ll tl, ll tr, ll l, ll r) {
if (r < tl || l > tr) return inf;
if (l <= tl && r >= tr) return tree[k];
ll mid = tl + (tr - tl) / 2;
return min(range_min(2*k, tl, mid, l, r), range_min(2*k+1, mid+1, tr, l, r));
}
};
struct symbol {
ll c = -1;
ll l0 = inf, r0 = -inf, l1 = inf, r1 = -inf;
bool operator<(const symbol &o) const {
return l0 < o.r0 && l1 < o.r1;
}
};
vector<int> ucs(vector<int> a, vector<int> b) {
ll n = sz(a), m = sz(b);
vector<symbol> syms(2e5+1);
for (ll i = 0; i < n; i++) {
auto &s = syms[a[i]];
s.l0 = min(s.l0, i);
s.r0 = max(s.r0, i);
}
for (ll i = 0; i < m; i++) {
auto &s = syms[b[i]];
s.l1 = min(s.l1, i);
s.r1 = max(s.r1, i);
}
vector<symbol> tmp;
for (ll i = 0; i < sz(syms); i++) {
if (syms[i].l0 == inf || syms[i].l1 == inf) continue;
tmp.push_back(syms[i]);
tmp.back().c = i;
}
syms = tmp;
segtree mn0(n), mx0(n), mn1(m), mx1(m);
for (auto &s : syms) {
if (s.l0 == s.r0) {
mn0.point_set(s.l0, s.l1);
mx0.point_set(s.l0, -s.r1);
}
if (s.l1 == s.r1) {
mn1.point_set(s.l1, s.l0);
mx1.point_set(s.l1, -s.r0);
}
}
for (auto &s : syms) {
bool ls = false, gr = false;
if (s.l0 < s.r0) {
ls = mn0.range_min(s.l0, s.r0) < s.l1;
gr = -mx0.range_min(s.l0, s.r0) > s.l1;
}
else if (s.l1 < s.r1) {
ls = mn1.range_min(s.l1, s.r1) < s.l0;
gr = -mx1.range_min(s.l1, s.r1) > s.l0;
}
if (ls && gr)
return {-1};
}
sort(all(syms));
ll i = 0, j = 0;
for (auto &s : syms) {
while (i < n && a[i] != s.c) i++;
while (j < m && b[j] != s.c) j++;
if (i++ >= n || j++ >= m) return {-1};
}
vector<int> res;
for (auto &s : syms) res.push_back(s.c);
return res;
}
