#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 ucs(vi A, vi B) {
vi 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 ret;
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) {
ret.pb(x), w_a.pop_back(), have[x]++, remainding[x]--;
} else {
ret.pb(y), w_b.pop_back(), have[y]++, remainding[y]--;
}
}
while (!w_a.empty()) ret.pb(w_a.back()), w_a.pop_back();
while (!w_b.empty()) ret.pb(w_b.back()), w_b.pop_back();
if (!is_subseq(ret, A) || !is_subseq(ret, B)) return vi{-1};
return ret;
}
