#include "hieroglyphs.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
bool contains(vector<int> a, vector<int> b)
{
ll ptr = 0;
for (ll i : a)
{
while (ptr < b.size() and b[ptr] != i) ptr++;
if (ptr == b.size()) return false;
}
return true;
}
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 (int x : a)
cnta[x]++;
for (int x : b)
cntb[x]++;
ll z = min(cnta[0], cntb[0]);
ll o = min(cnta[1], cntb[1]);
const ll INF = 1e18;
vector<array<ll, 2>> nxtA(n + 2), nxtB(m + 2);
nxtA[n][0] = nxtA[n][1] = INF;
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] = INF;
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 = z, orr = o;
bool uniq = true;
vector<int> res;
res.reserve(z + o);
for (ll k = 0; k < z + o; 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};
}
if (zr or orr) return {-1};
if (!contains(res, a) or !contains(res, b)) return {-1};
return res;
}
