#include "hieroglyphs.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
std::vector<int> ucs(std::vector<int> a, std::vector<int> b)
{
if (a.size() > b.size()) swap(a, b);
ll n = a.size(), m = b.size();
ll cnta[2] = {0, 0}, cntb[2] = {0, 0};
for (ll i = 0; i < n; i++) cnta[a[i]]++;
for (ll i = 0; i < m; i++) cntb[b[i]]++;
if (min(cnta[0], cntb[0]) + min(cnta[1], cntb[1]) == n)
{
ll ptr = 0;
for (ll i : a)
{
while (ptr < m and b[ptr] != i) ptr++;
if (ptr == m) return {-1};
ptr++;
}
return a;
}
ll zero = min(cnta[0], cntb[0]), one = min(cnta[1], cntb[1]);
vector<array<ll,2>> nxtA(n+2), nxtB(m+2);
nxtA[n][0] = nxtA[n][1] = 1e18;
for (ll i = n - 1; i >= 0; i--)
{
nxtA[i] = nxtA[i + 1];
nxtA[i][a[i]] = i + 1;
}
nxtB[m][0] = nxtB[m][1] = 1e18;
for (ll i = m - 1; i >= 0; i--)
{
nxtB[i] = nxtB[i + 1];
nxtB[i][b[i]] = i + 1;
}
vector<ll> suf0A(n+2), suf1A(n+2), suf0B(m+2), suf1B(m+2);
for (ll i = n - 1; i >= 0; i--)
{
suf0A[i] = suf0A[i + 1] + (a[i] == 0);
suf1A[i] = suf1A[i + 1] + (a[i] == 1);
}
for (ll i = m - 1; i >= 0; i--)
{
suf0B[i] = suf0B[i + 1] + (b[i] == 0);
suf1B[i] = suf1B[i + 1] + (b[i] == 1);
}
ll pa = 0, pb = 0;
ll zr = zero, orr = one;
bool uniq = true;
vector<int> res;
for (ll k = 0; k < zero + one; k++)
{
ll na0 = nxtA[pa][0], nb0 = nxtB[pb][0];
bool can0 = zr > 0 && na0 <= n && nb0 <= m
&& suf1A[na0] >= orr && suf1B[nb0] >= orr;
ll na1 = nxtA[pa][1], nb1 = nxtB[pb][1];
bool can1 = orr > 0 && na1 <= n && nb1 <= m
&& suf0A[na1] >= zr && suf0B[nb1] >= zr;
if (can0 && can1)
return {-1};
if (can0)
{
res.push_back(0);
pa = na0; pb = nb0;
zr--;
}
else if (can1)
{
res.push_back(1);
pa = na1; pb = nb1;
orr--;
}
else
return {-1};
}
return res;
}
