#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;
symbol(ll c, ll l0, ll r0, ll l1, ll r1) : c(c), l0(l0), r0(r0), l1(l1), r1(r1) { }
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<vector<ll>> ids0(2e5+1), ids1(2e5+1);
for (ll i = 0; i < n; i++) {
ids0[a[i]].push_back(i);
}
for (ll i = 0; i < m; i++) {
ids1[b[i]].push_back(i);
}
vector<symbol> syms;
for (ll i = 0; i < sz(syms); i++) {
if (sz(ids0[i]) < sz(ids1[i])) {
ll diff = sz(ids1[i]) - sz(ids0[i]);
for (ll j = 0; j < sz(ids0[i]); j++) {
syms.emplace_back(i, ids0[i][j], ids0[i][j], ids1[i][j], ids1[i][j+diff]);
}
}
else {
ll diff = sz(ids0[i]) - sz(ids1[i]);
for (ll j = 0; j < sz(ids1[i]); j++) {
syms.emplace_back(i, ids0[i][j], ids0[i][j+diff], ids1[i][j], ids1[i][j]);
}
}
}
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;
}
