#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;
int asz, bsz;
int l[maxn], r[maxn];
vector<int> vec[maxn];
int asum[maxn][2], bsum[maxn][2];
int aqry(int val, int l, int r) {
if (l > r) return 0;
int ret = asum[r][val];
if (l != 0) ret -= asum[l-1][val];
return ret;
// return upper_bound(apos[val].begin(), apos[val].end(), r) - lower_bound(apos[val].begin(), apos[val].end(), l);
}
int bqry(int val, int l, int r) {
if (l > r) return 0;
int ret = bsum[r][val];
if (l != 0) ret -= bsum[l-1][val];
return ret;
// return upper_bound(bpos[val].begin(), bpos[val].end(), r) - lower_bound(bpos[val].begin(), bpos[val].end(), l);
}
int siz;
bool ok(int id1, int id2) {
int al = l[id1] + 1, ar = r[id2] - 1;
int bl = bcrit[id1].second + 1, br = bcrit[id2].second - 1;
// int al = l[id] + 1, ar = r[id+1] - 1;
// int bl = bcrit[id].second + 1, br = bcrit[id+1].second - 1;
vector<int> vals;
// for (int i=bl;i<=br;i++) vals.push_back(b[i]);
// sort(vals.begin(), vals.end());
// vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i=0;i<=1;i++) if (afreq[i] < bfreq[i]) vals.push_back(i);
int cnt = 0;
for (int i:vals) if (afreq[i] < bfreq[i]) cnt += min(aqry(i, al, ar), bqry(i, bl, br));
// cout << cnt << endl;
// return (cnt == vec[id].size());
// cout << id1 << " " << id2 << endl;
// int siz = 0;
// cout << siz << endl;
// for (int i=id1;i<id2;i++) siz += vec[i].size();
return (cnt == siz);
}
vector<int> ucs(vector<int> A, vector<int> B) {
for (int i:A) afreq[i]++;
for (int i:B) bfreq[i]++;
a.push_back(2e5 + 1), b.push_back(2e5 + 1);
for (int i:A) if (bfreq[i]) a.push_back(i);
for (int i:B) if (afreq[i]) b.push_back(i);
a.push_back(2e5 + 2), b.push_back(2e5 + 2);
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});
for (int i=0;i<m;i++) if (bfreq[b[i]] <= afreq[b[i]]) bcrit.push_back({b[i], i});
for (int i=0;i<=1;i++) {
for (int j=0;j<n;j++) asum[j][i] = (a[j] == i);
for (int j=1;j<n;j++) asum[j][i] += asum[j-1][i];
for (int j=0;j<m;j++) bsum[j][i] = (b[j] == i);
for (int j=1;j<m;j++) bsum[j][i] += bsum[j-1][i];
}
asz = acrit.size(), bsz = bcrit.size();
for (int i=0;i<n;i++) apos[a[i]].push_back(i);
for (int i=0;i<m;i++) bpos[b[i]].push_back(i);
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;
pt = -1;
for (int i=0;i<n;i++) if (pt+1 < bsz && bcrit[pt+1].first == a[i]) pt++, l[pt] = i;
if (pt != bsz-1) return {-1};
vector<int> ans;
int apt = -1, bpt = -1, nxt = -1;
for (int i=0;i<bsz;i++) {
auto [val, pos] = bcrit[i];
// cout << "i " << i << endl;
while (apt+1 < asz && acrit[apt+1].second < r[i] && bpt < pos) {
bpt++;
if (b[bpt] == acrit[apt+1].first) {
vec[i-1].push_back({b[bpt]});
ans.push_back(b[bpt]);
apt++;
// cout << acrit[apt].second << endl;
}
}
if (i != 0 && i != bsz-1) ans.push_back(val);
nxt = *upper_bound(apos[val].begin(), apos[val].end(), nxt);
if (apt != -1) nxt = max(*upper_bound(apos[val].begin(), apos[val].end(), acrit[apt].second), nxt);
// cout << "thing " << i-1 << " " << val << " " << apt << endl;
// cout << acrit[apt].second << " " << acrit[apt+1].second << " " << nxt << endl;
if (apt+1 < asz && acrit[apt+1].second < nxt) return {-1};
bpt = pos;
}
if (ans.size() + 2 != asz + bsz) return {-1};
// for (int i=0;i<bsz-1;i++) if (!ok(i)) return {-1};
for (int i=0;i<bsz-1;i++) {
siz = 0;
for (int j=i+1;j<bsz;j++) {
siz += vec[j-1].size();
if (!ok(i, j)) return {-1};
}
}
// for (int i=0;i<bsz-1;i++) if (!ok(i, i+1)) return {-1};
return ans;
}
