#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxval = 2e5 + 5;
int n, m;
vector<int> a, b;
int afreq[maxval], bfreq[maxval];
vector<int> apos[maxval], bpos[maxval];
vector<pair<int,int>> acrit, bcrit;
bool aiscrit[maxn], biscrit[maxn];
int asz, bsz;
int r[maxn];
vector<int> ucs(vector<int> A, vector<int> B) {
for (int i:A) afreq[i]++;
for (int i:B) bfreq[i]++;
for (int i:A) if (bfreq[i]) a.push_back(i);
for (int i:B) if (afreq[i]) b.push_back(i);
n = a.size(), m = b.size();
for (int i=0;i<n;i++) if (afreq[a[i]] <= bfreq[a[i]]) {
acrit.push_back({a[i], i});
aiscrit[i] = true;
}
for (int i=0;i<m;i++) if (bfreq[b[i]] <= afreq[b[i]]) {
bcrit.push_back({a[i], i});
biscrit[i] = true;
}
asz = acrit.size(), bsz = bcrit.size();
int pt = bsz;
for (int i=n-1;i>=0;i--) {
if (pt-1 >= 0 && bcrit[pt-1].first == a[i]) {
pt--, r[pt] = i;
}
}
vector<int> ans;
int apt = -1, bpt = -1;
for (int i=0;i<bsz;i++) {
auto [val, pos] = bcrit[i];
while (apt+1 < asz && acrit[apt+1].second < r[i] && bpt < pos) {
bpt++;
if (b[bpt] == acrit[apt+1].first) {
ans.push_back({b[bpt]});
apt++;
}
}
ans.push_back(val);
if (afreq[val] == bfreq[val]) apt++;
bpt = pos;
}
while (apt+1 < asz) {
apt++;
ans.push_back(acrit[apt].first);
}
return ans;
}
