#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
using vi = vector<ll>;
const ll Nm = 2e5+5;
map<ll,ll> xopn,yopn; //open on x/y: # -> count
set<ll> sovlp; //set of overlap
set<ll> xblk,yblk; //x/y blocked: cannot do GREATER than this term
void insx(ll x0) {
if (xopn.find(x0)==xopn.end()) {
xopn[x0]=0;
}
xopn[x0]++;
if (xopn.find(x0)!=xopn.end() && yopn.find(x0)!=yopn.end()) {
sovlp.insert(x0);
}
}
void insy(ll x0) {
if (yopn.find(x0)==yopn.end()) {
yopn[x0]=0;
}
yopn[x0]++;
if (xopn.find(x0)!=xopn.end() && yopn.find(x0)!=yopn.end()) {
sovlp.insert(x0);
}
}
void delx(ll x0) {
xopn[x0]--;
if (xopn[x0]==0) {
xopn.erase(xopn.find(x0));
if (sovlp.find(x0)!=sovlp.end()) {
sovlp.erase(sovlp.find(x0));
}
}
}
void dely(ll x0) {
yopn[x0]--;
if (yopn[x0]==0) {
yopn.erase(yopn.find(x0));
if (sovlp.find(x0)!=sovlp.end()) {
sovlp.erase(sovlp.find(x0));
}
}
}
vector<int> ucs(vector<int> A, vector<int> B) {
xopn.clear(); yopn.clear(); sovlp.clear(); xblk.clear(); yblk.clear();
vi fail = {-1};
vi ans;
ll N = A.size(); ll M = B.size();
vector<ll> posa[Nm]; //posa[val] -> locations of val in order
vector<ll> posb[Nm];
set<ll> rpa[Nm]; //remaining positions of val
set<ll> rpb[Nm];
ll FLEN = 0; ll CLEN = 0;
for (ll i=0;i<N;i++) {
posa[A[i]].push_back(i);
rpa[A[i]].insert(i);
}
for (ll i=0;i<M;i++) {
posb[B[i]].push_back(i);
rpb[B[i]].insert(i);
}
vector<ll> fnum(Nm,0);
vector<ll> cnum(Nm,0);
for (ll x=0;x<Nm;x++) {
fnum[x]=min((ll)posa[x].size(),(ll)posb[x].size());
}
ll xprc = 0; ll yprc = 0; //min x/y not processsed (initially unlocked by algo)
ll xcvr = 0; ll ycvr = 0; //min x,y not covered ("walked over" by algo)
xblk.insert(N-1); yblk.insert(M-1);
for (ll x=0;x<Nm;x++) {
ll mn = min((ll)posa[x].size(),(ll)posb[x].size());
FLEN += mn;
// if (mn>0) {
// xblk.insert(posa[x][posa[x].size()-mn]);
// yblk.insert(posb[x][posb[x].size()-mn]);
// }
for (ll d=((ll)posa[x].size()-mn);d<((ll)posa[x].size());d++) {
xblk.insert(posa[x][d]);
//cout << "x="<<x<<", posa trm="<<posa[x][d]<<"\n";
}
for (ll d=((ll)posb[x].size()-mn);d<((ll)posb[x].size());d++) {
yblk.insert(posb[x][d]);
//cout << "x="<<x<<", posb trm="<<posb[x][d]<<"\n";
}
}
while (FLEN>CLEN) {
//cout << "loop start\n";
//cout << "xblk: "<<(*(xblk.begin()))<<"\n";
//cout << "yblk: "<<(*(yblk.begin()))<<"\n";
while (xprc<=(*(xblk.begin()))) {
insx(A[xprc]); xprc++;
}
while (yprc<=(*(yblk.begin()))) {
insy(B[yprc]); yprc++;
}
// cout << "sovlp elems: \n";
// for (ll x0: sovlp) {
// cout << x0 << "=solvp term\n";
// }
if (sovlp.size()!=1) {
return fail;
}
ll v0 = *(sovlp.begin()); ans.push_back(v0); CLEN++;
ll xfc = *(rpa[v0].begin());
ll yfc = *(rpb[v0].begin());
//cout << "xfc="<<xfc<<", yfc="<<yfc<<"\n";
// if ((ll)fnum[v0]<(ll)(posb[v0].size()-posa[v0].size())) {
// //modify this
// if (yblk.find(posb[v0][fnum[v0]])!=yblk.end()) {
// yblk.erase(yblk.find(posb[v0][fnum[v0]]));
// }
// // if ((ll)fnum[v0]<(ll)(posb[v0].size()-posa[v0].size()-1)) {
// // yblk.insert(posb[v0][fnum[v0]+1]);
// // }
// }
if (posb[v0].size()>posa[v0].size()) {
if (yblk.find(posb[v0][(ll)posb[v0].size()-(ll)posa[v0].size()+cnum[v0]])!=yblk.end()) {
yblk.erase(yblk.find(posb[v0][(ll)posb[v0].size()-(ll)posa[v0].size()+cnum[v0]]));
}
}
// if ((ll)fnum[v0]<(ll)(posa[v0].size()-posb[v0].size())) {
// if (xblk.find(posa[v0][fnum[v0]])!=xblk.end()) {
// xblk.erase(xblk.find(posa[v0][fnum[v0]]));
// }
// // if ((ll)fnum[v0]<(ll)(posa[v0].size()-posb[v0].size()-1)) {
// // xblk.insert(posa[v0][fnum[v0]+1]);
// // }
// }
if (posa[v0].size()>posb[v0].size()) {
// cout << "xidx = " <<((ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0])<<"\n";
// cout << "deleting x block at: "<<posa[v0][(ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0]]<<"\n";
if (xblk.find(posa[v0][(ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0]])!=xblk.end()) {
xblk.erase(xblk.find(posa[v0][(ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0]]));
}
}
cnum[v0]++;
while (xcvr<=xfc) {
delx(A[xcvr]);
//cout << "delx: "<<A[xcvr]<<"\n";
rpa[A[xcvr]].erase(rpa[A[xcvr]].find(xcvr));
if (xblk.find(xcvr)!=xblk.end()) {
xblk.erase(xblk.find(xcvr));
}
xcvr++;
}
while (ycvr<=yfc) {
dely(B[ycvr]);
//cout << "dely: "<<B[ycvr]<<"\n";
rpb[B[ycvr]].erase(rpb[B[ycvr]].find(ycvr));
if (yblk.find(ycvr)!=yblk.end()) {
yblk.erase(yblk.find(ycvr));
}
ycvr++;
}
}
return ans;
}
