#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> I = {-1};
struct segment_tree{
int n;
int M[300000];
void init(int N, int l, int r){
if(l == r)M[N] = n;
else{
init(2*N, l, (l+r)/2);
init(2*N+1, (l+r)/2+1, r);
}
}
void update(int N, int x, int y, int l, int r){
if(x < l || x > r)return;
if(l == x && x == r){
M[N] = min(M[N], y);
return;
}
update(2*N, x, y, l, (l+r)/2);
update(2*N+1, x, y, (l+r)/2+1, r);
M[N] = min(M[2*N], M[2*N+1]);
}
int get_left(int N, int z, int l, int r){
if(z < l)return n;
if(z >= r)return M[N];
return min(get_left(2*N, z, l, (l+r)/2), get_left(2*N+1, z, (l+r)/2+1, r));
}
int get_right(int N, int z, int l, int r){
if(z > r)return n;
if(z <= l)return M[N];
return min(get_right(2*N, z, l, (l+r)/2), get_right(2*N+1, z, (l+r)/2+1, r));
}
} T;
struct indexes{
vector<int> A[200002], B[200002], C, D, E;
int F[200002];
vector<pair<pair<int, int>, pair<int, int>>> e, f;
bool is_sq(int a, int b, int c, int d){
return A[a][c-1] < A[b][A[b].size()-d] && B[a][c-1] < B[b][B[b].size()-d];
}
bool init(vector<int> a, vector<int> b){
for(int i = 0; i < a.size(); i++)A[a[i]].push_back(i);
for(int i = 0; i < b.size(); i++)B[b[i]].push_back(i);
C.clear(), D.clear(), E.clear();
for(int i:a)if(A[i].size() <= B[i].size())C.push_back(i);
for(int i:b)if(A[i].size() >= B[i].size())D.push_back(i);
int N = C.size();
int M = D.size();
int x = 0, y = 0;
while(x < N || y < M){
if(x || y)F[E[E.size()-1]]++;
e.push_back(make_pair(make_pair(0, 0), make_pair(0, 0)));
f.push_back(make_pair(make_pair(0, 0), make_pair(0, 0)));
if(x == N){
E.push_back(D[y++]);
continue;
}
if(y == M){
E.push_back(C[x++]);
continue;
}
if(A[C[x]].size() == B[C[x]].size() || A[D[y]].size() == B[D[y]].size()){
if(C[x] == D[y]){
E.push_back(D[y++]);
x++;
continue;
}
if(A[C[x]].size() != B[C[x]].size()){
E.push_back(C[x++]);
continue;
}
if(A[D[y]].size() != B[D[y]].size()){
E.push_back(D[y++]);
continue;
}
return true;
}
bool X = is_sq(C[x], D[y], F[C[x]]+1, B[D[y]].size()-F[D[y]]), Y = is_sq(D[y], C[x], F[D[y]]+1, A[C[x]].size()-F[C[x]]);
if(X && Y)return true;
if(Y){
E.push_back(D[y++]);
continue;
}
if(X){
E.push_back(C[x++]);
continue;
}
return true;
}
return false;
}
bool check_sq(vector<int> a, vector<int> b){
for(int i:E)F[i] = 0;
T.init(1, 1, T.n);
for(int i = 0; i < E.size(); i++){
if(!F[E[i]])e[i].first.first = A[E[i]][0];
else{
int t = T.get_right(1, F[E[i]], 1, T.n);
int l = 0, r = A[E[i]].size()-1;
while(l < r){
int c = (l+r)/2;
if(A[E[i]][c] > t)r = c;
else l = c+1;
}
e[i].first.first = A[E[i]][l];
}
F[E[i]] = i+1;
T.update(1, i+1, e[i].first.first, 1, T.n);
}
for(int i:E)F[i] = T.n;
T.init(1, 1, T.n);
for(int i = E.size()-1; i >= 0; i--){
if(F[E[i]] == T.n)e[i].first.second = A[E[i]][A[E[i]].size()-1];
else{
int t = T.n-T.get_left(1, F[E[i]]+1, 1, T.n);
int l = 0, r = A[E[i]].size()-1;
while(l < r){
int c = (l+r+1)/2;
if(A[E[i]][c] < t)l = c;
else r = c-1;
}
e[i].first.second = A[E[i]][r];
}
F[E[i]] = i;
T.update(1, i+1, T.n-e[i].first.second, 1, T.n);
}
for(int i:E)F[i] = 0;
T.init(1, 1, T.n);
for(int i = 0; i < E.size(); i++){
if(!F[E[i]])e[i].second.first = B[E[i]][0];
else{
int t = T.get_right(1, F[E[i]], 1, T.n);
int l = 0, r = B[E[i]].size()-1;
while(l < r){
int c = (l+r)/2;
if(B[E[i]][c] > t)r = c;
else l = c+1;
}
e[i].second.first = B[E[i]][l];
}
F[E[i]] = i+1;
T.update(1, i+1, e[i].second.first, 1, T.n);
}
for(int i:E)F[i] = T.n;
T.init(1, 1, T.n);
for(int i = E.size()-1; i >= 0; i--){
if(F[E[i]] == T.n)e[i].second.second = B[E[i]][B[E[i]].size()-1];
else{
int t = T.n-T.get_left(1, F[E[i]]+1, 1, T.n);
int l = 0, r = B[E[i]].size()-1;
while(l < r){
int c = (l+r+1)/2;
if(B[E[i]][c] < t)l = c;
else r = c-1;
}
e[i].second.second = B[E[i]][r];
}
F[E[i]] = i;
T.update(1, i+1, T.n-e[i].second.second, 1, T.n);
}
int c, d;
c = 0, d = 0;
for(int i = 0; i < E.size(); i++){
while(a[c] != E[i])c++;
f[i].first.first = c++;
while(b[d] != E[i])d++;
f[i].second.first = d++;
}
c = a.size()-1, d = b.size()-1;
for(int i = E.size()-1; i >= 0; i--){
while(a[c] != E[i])c--;
f[i].first.second = c--;
while(b[d] != E[i])d--;
f[i].second.second = d--;
}
T.n = a.size();
T.init(1, 1, T.n);
for(int i = 0; i < E.size(); i++){
if(A[E[i]].size() <= B[E[i]].size())T.update(1, f[i].first.first, e[i].second.first, 1, T.n);
if(B[E[i]].size() <= A[E[i]].size() && f[i].second.second <= T.get_right(1, e[i].first.second, 1, T.n))return true;
}
T.n = b.size();
T.init(1, 1, T.n);
for(int i = 0; i < E.size(); i++){
if(B[E[i]].size() <= A[E[i]].size())T.update(1, f[i].second.first, e[i].first.first, 1, T.n);
if(A[E[i]].size() <= B[E[i]].size() && f[i].first.second <= T.get_right(1, e[i].second.second, 1, T.n))return true;
}
return false;
}
} H;
vector<int> ucs(vector<int> A, vector<int> B) {
int N = A.size(), M = B.size();
if(H.init(A, B))return I;
T.n = H.E.size();
if(H.check_sq(A, B))return I;
return H.E;
}
