#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
static const int V = 200002;
static const int INF = 1000000007;
struct SegMin {
int n;
vector<int> st;
void init(int N){
n = N;
st.assign(4*n+4, INF);
}
void upd(int p, int l, int r, int idx, int val){
if(l==r){ st[p] = min(st[p], val); return; }
int m=(l+r)>>1;
if(idx<=m) upd(p<<1,l,m,idx,val);
else upd(p<<1|1,m+1,r,idx,val);
st[p]=min(st[p<<1],st[p<<1|1]);
}
int ql(int p,int l,int r,int q){
if(q>=r) return st[p];
int m=(l+r)>>1;
if(q<=m) return min(ql(p<<1,l,m,q), st[p<<1|1]);
return ql(p<<1|1,m+1,r,q);
}
int qr(int p,int l,int r,int q){
if(q<=l) return st[p];
int m=(l+r)>>1;
if(q>m) return min(st[p<<1], qr(p<<1|1,m+1,r,q));
return qr(p<<1,l,m,q);
}
};
static SegMin seg;
static inline bool is_sq(const vector<int>& Ax, const vector<int>& Ay,
const vector<int>& Bx, const vector<int>& By,
int k, int l){
if((int)Ax.size() < k || (int)Ay.size() < l) return false;
if((int)Bx.size() < k || (int)By.size() < l) return false;
int ax = Ax[k-1], ay = Ay[(int)Ay.size()-l];
int bx = Bx[k-1], by = By[(int)By.size()-l];
return ax < ay && bx < by;
}
vector<int> ucs(vector<int> A, vector<int> B) {
int N = (int)A.size(), M = (int)B.size();
vector<vector<int>> posA(V), posB(V);
vector<int> ca(V,0), cb(V,0);
for(int i=0;i<N;i++){ int x=A[i]; if(0<=x && x<V){ ca[x]++; posA[x].push_back(i); } }
for(int i=0;i<M;i++){ int x=B[i]; if(0<=x && x<V){ cb[x]++; posB[x].push_back(i); } }
vector<char> common(V,0), weakA(V,0);
for(int x=0;x<V;x++){
if(ca[x] && cb[x]){
common[x]=1;
weakA[x] = (ca[x] <= cb[x]);
}
}
vector<int> C, D;
C.reserve(N);
D.reserve(M);
for(int x: A) if(common[x] && weakA[x]) C.push_back(x);
for(int x: B) if(common[x] && !weakA[x]) D.push_back(x);
vector<int> used(V,0);
vector<int> E;
E.reserve(C.size() + D.size());
int i=0,j=0;
while(i < (int)C.size() || j < (int)D.size()){
if(!E.empty()) used[E.back()]++;
if(i==(int)C.size()){ E.push_back(D[j++]); continue; }
if(j==(int)D.size()){ E.push_back(C[i++]); continue; }
int x = C[i], y = D[j];
if(ca[x]==cb[x] || ca[y]==cb[y]){
if(x==y){ E.push_back(x); i++; j++; continue; }
if(ca[x]!=cb[x]){ E.push_back(x); i++; continue; }
if(ca[y]!=cb[y]){ E.push_back(y); j++; continue; }
return vector<int>{-1};
}
int kx = used[x] + 1;
int ly = cb[y] - used[y];
int ky = used[y] + 1;
int lx = ca[x] - used[x];
bool X = is_sq(posA[x], posA[y], posB[x], posB[y], kx, ly);
bool Y = is_sq(posA[y], posA[x], posB[y], posB[x], ky, lx);
if(X && Y) return vector<int>{-1};
if(Y){ E.push_back(y); j++; }
else if(X){ E.push_back(x); i++; }
else return vector<int>{-1};
}
int L = (int)E.size();
vector<int> fA1(L), fA2(L), fB1(L), fB2(L);
{
int p=0;
for(int t=0;t<L;t++){
while(p<N && A[p]!=E[t]) p++;
if(p==N) return vector<int>{-1};
fA1[t]=p++;
}
p=N-1;
for(int t=L-1;t>=0;t--){
while(p>=0 && A[p]!=E[t]) p--;
if(p<0) return vector<int>{-1};
fA2[t]=p--;
}
}
{
int p=0;
for(int t=0;t<L;t++){
while(p<M && B[p]!=E[t]) p++;
if(p==M) return vector<int>{-1};
fB1[t]=p++;
}
p=M-1;
for(int t=L-1;t>=0;t--){
while(p>=0 && B[p]!=E[t]) p--;
if(p<0) return vector<int>{-1};
fB2[t]=p--;
}
}
vector<int> last(V,-1), prv(L,-1);
for(int t=0;t<L;t++){
int x=E[t];
prv[t]=last[x];
last[x]=t;
}
auto build_side = [&](const vector<int>& S, int n, const vector<vector<int>>& pos, bool rev)->vector<int>{
int m=(int)S.size();
int SZ=1; while(SZ<m) SZ<<=1;
vector<int> segv(2*SZ, INF);
auto seg_set = [&](int idx,int val){
int p=idx+SZ; segv[p]=val;
for(p>>=1;p;p>>=1) segv[p]=min(segv[p<<1],segv[p<<1|1]);
};
auto seg_q = [&](int l,int r){
if(l>r) return INF;
l+=SZ; r+=SZ;
int res=INF;
while(l<=r){
if(l&1) res=min(res, segv[l++]);
if(!(r&1)) res=min(res, segv[r--]);
l>>=1; r>>=1;
}
return res;
};
vector<int> dp(m, INF);
for(int t=0;t<m;t++){
int x=S[t];
int mp = (prv[t]==-1)? -1 : seg_q(prv[t], t-1);
if(mp>=INF){
dp[t]=INF;
}else{
const auto &vec=pos[x];
if(!rev){
auto it = upper_bound(vec.begin(), vec.end(), mp);
dp[t] = (it==vec.end()? INF : *it);
}else{
int bound = (n-1) - mp;
auto it = lower_bound(vec.begin(), vec.end(), bound);
if(it==vec.begin()) dp[t]=INF;
else { --it; dp[t]=(n-1)-*it; }
}
}
seg_set(t, dp[t]);
}
return dp;
};
vector<int> VL_A = build_side(E, N, posA, false);
vector<int> VL_B = build_side(E, M, posB, false);
vector<int> Er = E;
reverse(Er.begin(), Er.end());
vector<int> VLAr = build_side(Er, N, posA, true);
vector<int> VLBr = build_side(Er, M, posB, true);
vector<int> VR_A(L,-1), VR_B(L,-1);
for(int t=0;t<L;t++){
int a = VLAr[L-1-t];
int b = VLBr[L-1-t];
VR_A[t] = (a>=INF? -1 : (N-1)-a);
VR_B[t] = (b>=INF? -1 : (M-1)-b);
}
vector<int> wL(L), wR(L);
for(int t=0;t<L;t++){
int x=E[t];
if(weakA[x]){ wL[t]=fA1[t]; wR[t]=fA2[t]; }
else { wL[t]=fB1[t]; wR[t]=fB2[t]; }
}
seg.init(N+2);
for(int t=0;t<L;t++){
int x=E[t];
if(!weakA[x]){
int q = seg.qr(1,1,seg.n, VL_A[t]+2);
if(q < wL[t]) return vector<int>{-1};
}
if(weakA[x] && VR_B[t]!=-1){
seg.upd(1,1,seg.n, wR[t]+1, (seg.n-1)-VR_B[t]);
}
}
seg.init(M+2);
for(int t=0;t<L;t++){
int x=E[t];
if(weakA[x]){
int q = seg.qr(1,1,seg.n, VL_B[t]+2);
if(q < wL[t]) return vector<int>{-1};
}
if(!weakA[x] && VR_A[t]!=-1){
seg.upd(1,1,seg.n, wR[t]+1, (seg.n-1)-VR_A[t]);
}
}
return E;
}
