#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
using vi = vector<int>;
using vb = vector<bool>;
#define pb push_back
#define eb emplace_back
struct FTree {
int n;
vi ft;
FTree(int _n) : n(_n + 9), ft(n, 0) {}
void update(int pos, int val) {
for (++pos; pos < n; pos += pos & -pos) ft[pos] += val;
}
int get(int pos) {
int s = 0;
for (; pos > 0; pos -= pos & -pos) s += ft[pos];
return s;
}
int query(int l, int r) {
return get(r) - get(l);
}
};
const int M = 2e5 + 9;
vi buildFreq(vi &a) {
vi freq(M, 0);
for (int x : a) freq[x]++;
return freq;
}
vi subsequence(vi &a, vb &type, bool active) {
vi w;
dforn(i, sz(a)) if (type[a[i]] == active) w.pb(a[i]);
return w;
}
vector<vi> buildWhere(vi &a) {
vector<vi> where(M);
forn(i, sz(a)) where[a[i]].pb(i);
return where;
}
bool check(int x, int c_x, int y, int c_y, const vector<vi> &where) {
if (c_x == 0) return sz(where[y]) >= c_y;
if (c_y == 0) return sz(where[x]) >= c_x;
return sz(where[x]) >= c_x && sz(where[y]) >= c_y && where[x][c_x - 1] < where[y][sz(where[y]) - c_y];
}
bool common_subsecuence(int x, int c_x, int y, int c_y, const vector<vi> &where_a, const vector<vi> &where_b) {
return check(x, c_x, y, c_y, where_a) && check(x, c_x, y, c_y, where_b);
}
bool is_subseq(vi &s, vi &a) {
int i = 0, j = 0;
while (i < sz(s) && j < sz(a)) {
if (s[i] == a[j]) i++;
j++;
}
return i == sz(s);
}
bool check(vi &A, vi &B, vi &cnt_a, vi &cnt_b, vector<vi> &where_a, vector<vi> &where_b) {
FTree ft(sz(A));
forn(i, sz(B)) { // B: x y x, A: y x y
int x = B[i];
if (cnt_b[x] == 2 && cnt_a[x] == 1) {
if (where_b[x][0] == i) ft.update(where_a[x][0], 1);
else ft.update(where_a[x][0], -1);
}
if (cnt_b[x] == 1 && cnt_a[x] == 2 && ft.query(where_a[x][0], where_a[x][1] + 1) > 0) {
return false;
}
}
return true;
}
vi clear(vi &a, vb &relevant) {
vi newA;
for (int x : a) if (relevant[x]) newA.pb(x);
return newA;
}
void compress(vi &a, vi &id, vi &val, int &m) {
forn(i, sz(a)) {
if (id[a[i]] == -1) {
val.pb(a[i]);
id[a[i]] = m++;
}
a[i] = id[a[i]];
}
}
bool checkQuadratic(vi &a, vi &b, vi &c, int v) {
const int n = sz(a), m = sz(b), l = sz(c);
vector<vi> nxt(l + 2, vi(v, l + 1));
dforn(i, l) {
nxt[i] = nxt[i + 1];
nxt[i][c[i]] = i + 1;
}
vector<vi> dp(n + 1, vi(m + 1, 0));
forn(i, n) forn(j, m) {
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
if (a[i] == b[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], nxt[dp[i][j]][a[i]]);
}
return dp[n][m] <= l;
}
vi ucs(vi A, vi B) {
vi cnt_a = buildFreq(A), cnt_b = buildFreq(B);
vb relevant(M, false);
forn(i, M) relevant[i] = min(cnt_a[i], cnt_b[i]) > 0;
A = clear(A, relevant), B = clear(B, relevant);
vi id(M, -1), val;
int m = 0;
compress(A, id, val, m);
compress(B, id, val, m);
cnt_a = buildFreq(A), cnt_b = buildFreq(B);
vector<vi> where_a = buildWhere(A), where_b = buildWhere(B);
bool flag = true;
forn(i, m) flag &= cnt_a[i] + cnt_b[i] <= 3;
if (flag && !check(A, B, cnt_a, cnt_b, where_a, where_b)) return vi{-1};
vb type(m);
forn(i, m) type[i] = cnt_a[i] <= cnt_b[i];
vi w_a = subsequence(A, type, true), w_b = subsequence(B, type, false);
vi have(m, 0), remainding(m);
forn(i, m) remainding[i] = min(cnt_a[i], cnt_b[i]);
vi c;
while (!w_a.empty() && !w_b.empty()) {
int x = w_a.back(), y = w_b.back();
bool X = common_subsecuence(x, have[x] + 1, y, remainding[y], where_a, where_b);
bool Y = common_subsecuence(y, have[y] + 1, x, remainding[x], where_a, where_b);
if (X && Y) return vi{-1};
if (X) {
c.pb(x), w_a.pop_back(), have[x]++, remainding[x]--;
} else {
c.pb(y), w_b.pop_back(), have[y]++, remainding[y]--;
}
}
while (!w_a.empty()) c.pb(w_a.back()), w_a.pop_back();
while (!w_b.empty()) c.pb(w_b.back()), w_b.pop_back();
if (!is_subseq(c, A) || !is_subseq(c, B)) return vi{-1};
if (max(sz(A), sz(B)) <= 3000 && !checkQuadratic(A, B, c, m)) return vi{-1};
vi ret(sz(c));
forn(i, sz(c)) ret[i] = val[c[i]];
return ret;
}
