#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
static const int SIG = 200001;
static const int INF = 1e9;
struct BITMax {
int n;
vector<int> bit;
BITMax(int n=0){ init(n); }
void init(int n_){
n = n_;
bit.assign(n+1, -1);
}
void upd(int pos, int val){
int i = n - pos;
for(; i <= n; i += i & -i) bit[i] = max(bit[i], val);
}
int query_suffix_gt(int th){
if(th >= n-1) return -1;
int lim = n - (th+1);
int res = -1;
for(int i = lim; i > 0; i -= i & -i) res = max(res, bit[i]);
return res;
}
};
static inline int next_pos(const vector<int>& v, int after){
auto it = upper_bound(v.begin(), v.end(), after);
if(it == v.end()) return INF;
return *it;
}
static vector<int> compute_VL(const vector<int>& S, const vector<vector<int>>& posS, const vector<int>& T){
int n = (int)S.size();
int m = (int)T.size();
vector<int> prev(m, -1);
static vector<int> last(SIG, -1);
for(int i=0;i<SIG;i++) last[i] = -1;
for(int i=0;i<m;i++){
int c = T[i];
prev[i] = last[c];
last[c] = i;
}
int SZ = 1;
while(SZ < m) SZ <<= 1;
vector<int> seg(2*SZ, INF);
auto seg_set = [&](int idx, int val){
int p = idx + SZ;
seg[p] = val;
for(p >>= 1; p; p >>= 1) seg[p] = min(seg[p<<1], seg[p<<1|1]);
};
auto seg_min = [&](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, seg[l++]);
if(!(r & 1)) res = min(res, seg[r--]);
l >>= 1; r >>= 1;
}
return res;
};
vector<int> dp(m, INF);
for(int i=0;i<m;i++){
int c = T[i];
int bestPrev;
if(prev[i] == -1){
bestPrev = min(-1, (i==0 ? INF : seg_min(0, i-1)));
} else {
bestPrev = seg_min(prev[i], i-1);
}
if(bestPrev >= INF) dp[i] = INF;
else dp[i] = next_pos(posS[c], bestPrev);
seg_set(i, dp[i]);
}
return dp;
}
static vector<int> compute_VR(const vector<int>& S, const vector<vector<int>>& posSr, const vector<int>& T){
int n = (int)S.size();
int m = (int)T.size();
vector<int> Tr = T;
reverse(Tr.begin(), Tr.end());
vector<int> VLr = compute_VL(vector<int>(), posSr, Tr);
vector<int> VR(m, -1);
for(int i=0;i<m;i++){
int x = VLr[m-1-i];
if(x >= INF) VR[i] = -1;
else VR[i] = n-1-x;
}
return VR;
}
static bool embed_left(const vector<int>& P, const vector<int>& S, vector<int>& out){
out.resize(P.size());
int p = 0;
for(int i=0;i<(int)P.size();i++){
int x = P[i];
while(p < (int)S.size() && S[p] != x) p++;
if(p == (int)S.size()) return false;
out[i] = p++;
}
return true;
}
static bool embed_right(const vector<int>& P, const vector<int>& S, vector<int>& out){
out.resize(P.size());
int p = (int)S.size()-1;
for(int i=(int)P.size()-1;i>=0;i--){
int x = P[i];
while(p >= 0 && S[p] != x) p--;
if(p < 0) return false;
out[i] = p--;
}
return true;
}
static inline bool block_common(
int x, int kx, int y, int ly,
const vector<vector<int>>& posA, const vector<vector<int>>& posB
){
const auto &Ax = posA[x], &Ay = posA[y];
const auto &Bx = posB[x], &By = posB[y];
if((int)Ax.size() < kx || (int)Ay.size() < ly) return false;
if((int)Bx.size() < kx || (int)By.size() < ly) return false;
int ax = Ax[kx-1];
int ay = Ay[(int)Ay.size() - ly];
int bx = Bx[kx-1];
int by = By[(int)By.size() - ly];
return ax < ay && bx < by;
}
vector<int> ucs(vector<int> A, vector<int> B) {
int N = (int)A.size(), M = (int)B.size();
vector<int> occA(SIG,0), occB(SIG,0);
vector<vector<int>> posA(SIG), posB(SIG);
vector<char> inA(SIG,0), inB(SIG,0);
for(int i=0;i<N;i++){
int x = A[i];
if(0<=x && x<SIG){
occA[x]++; posA[x].push_back(i); inA[x]=1;
}
}
for(int i=0;i<M;i++){
int x = B[i];
if(0<=x && x<SIG){
occB[x]++; posB[x].push_back(i); inB[x]=1;
}
}
vector<char> common(SIG,0), aweak(SIG,0);
for(int x=0;x<SIG;x++){
if(inA[x] && inB[x]){
common[x]=1;
aweak[x] = (occA[x] <= occB[x]);
}
}
vector<int> WA, WB;
WA.reserve(N); WB.reserve(M);
for(int x: A) if(common[x] && aweak[x]) WA.push_back(x);
for(int x: B) if(common[x] && !aweak[x]) WB.push_back(x);
vector<int> usedA(SIG,0), usedB(SIG,0);
vector<int> C;
C.reserve(WA.size() + WB.size());
int i=0, j=0;
while(i < (int)WA.size() && j < (int)WB.size()){
int x = WA[i], y = WB[j];
int k1 = usedA[x] + 1;
int l1 = occB[y] - usedB[y];
int k2 = usedB[y] + 1;
int l2 = occA[x] - usedA[x];
bool ok1 = block_common(x, k1, y, l1, posA, posB);
bool ok2 = block_common(y, k2, x, l2, posA, posB);
if(ok1 ^ ok2){
if(ok1){ C.push_back(x); usedA[x]++; i++; }
else { C.push_back(y); usedB[y]++; j++; }
} else {
return vector<int>{-1};
}
}
while(i < (int)WA.size()) C.push_back(WA[i++]);
while(j < (int)WB.size()) C.push_back(WB[j++]);
vector<int> LA, LB, RA, RB;
if(!embed_left(C, A, LA)) return vector<int>{-1};
if(!embed_left(C, B, LB)) return vector<int>{-1};
if(!embed_right(C, A, RA)) return vector<int>{-1};
if(!embed_right(C, B, RB)) return vector<int>{-1};
int L = (int)C.size();
vector<int> wL(L), wR(L);
for(int t=0;t<L;t++){
int x = C[t];
if(aweak[x]){ wL[t] = LA[t]; wR[t] = RA[t]; }
else { wL[t] = LB[t]; wR[t] = RB[t]; }
}
vector<vector<int>> posAr(SIG), posBr(SIG);
for(int x=0;x<SIG;x++){
if(!posA[x].empty()){
posAr[x].reserve(posA[x].size());
for(int p: posA[x]) posAr[x].push_back(N-1-p);
sort(posAr[x].begin(), posAr[x].end());
}
if(!posB[x].empty()){
posBr[x].reserve(posB[x].size());
for(int p: posB[x]) posBr[x].push_back(M-1-p);
sort(posBr[x].begin(), posBr[x].end());
}
}
vector<int> VL_A = compute_VL(A, posA, C);
vector<int> VL_B = compute_VL(B, posB, C);
vector<int> Cr = C; reverse(Cr.begin(), Cr.end());
vector<int> VL_Ar = compute_VL(vector<int>(), posAr, Cr);
vector<int> VL_Br = compute_VL(vector<int>(), posBr, Cr);
vector<int> VR_A(L, -1), VR_B(L, -1);
for(int t=0;t<L;t++){
int a = VL_Ar[L-1-t];
int b = VL_Br[L-1-t];
VR_A[t] = (a >= INF ? -1 : N-1-a);
VR_B[t] = (b >= INF ? -1 : M-1-b);
}
BITMax bitA(N), bitB(M);
for(int t=0;t<L;t++){
int x = C[t];
if(!aweak[x]){
int th = VL_A[t];
if(th < INF){
int best = bitA.query_suffix_gt(th);
if(best > wL[t]) return vector<int>{-1};
}
}
if(aweak[x] && VR_B[t] != -1){
bitA.upd(wR[t], VR_B[t]);
}
}
for(int t=0;t<L;t++){
int x = C[t];
if(aweak[x]){
int th = VL_B[t];
if(th < INF){
int best = bitB.query_suffix_gt(th);
if(best > wL[t]) return vector<int>{-1};
}
}
if(!aweak[x] && VR_A[t] != -1){
bitB.upd(wR[t], VR_A[t]);
}
}
return C;
}
