#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
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);
}
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);
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();
if (common_subsecuence(x, have[x] + 1, y, remainding[y], where_a, where_b)) {
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();
return ret;
}
