#include "hieroglyphs.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<int> pos1[200001];
vector<int> pos2[200001];
vector<int> idk(200001, INT_MAX);
void upd(int a, int c) {
while(a < idk.size()) {
idk[a] = min(idk[a],c);
a+=(a&(-a));
}
}
int calc(int a) {
int c = 0,ans = INT_MAX;
for(int i = 18; i >= 0; i--) {
if(c+(1 << i) <= a) {
c+=(1<<i);
ans = min(ans,idk[c]);
}
}
return ans;
}
int dude(int x, int a) {
if(pos1[x].size() == 0 || pos1[x][pos1[x].size()-1] < a) {
return -1;
}
int l = 0,r = pos1[x].size()-1;
while(l < r) {
int mid = (l+r)/2;
if(pos1[x][mid] >= a) {
r = mid;
}
else {
l = mid+1;
}
}
return pos1[x][l];
}
std::vector<int> ucs(std::vector<int> a, std::vector<int> b) {
vector<int> wow(0);
vector<int> wut(1,-1);
for(int i = 0; i < a.size(); i++) {
pos1[a[i]].push_back(i);
}
for(int i = 0; i < b.size(); i++) {
pos2[b[i]].push_back(i);
}
for(int i = 0; i < a.size(); i++) {
if(pos1[a[i]].size() <= pos2[a[i]].size()) {
wow.push_back(a[i]);
wut.push_back(i);
}
}
int y = wow.size()-1;
vector<int> banana(b.size());
for(int i = b.size()-1; i >= 0; i--) {
if(y >= 0 && b[i] == wow[y]) {
y--;
}
banana[i] = y+1;
}
vector<int> ans(0);
y = 1;
int l = 0;
for(int i = 0; i < b.size(); i++) {
if(pos1[b[i]].size() <= pos2[b[i]].size()) {
continue;
}
l = max(l,wut[banana[i]]+1);
int c = dude(b[i],l);
if(c == -1) {
return {-1};
}
l = max(l,c+1);
while(y < wut.size() && wut[y] < c) {
ans.push_back(wow[y-1]);
y++;
}
ans.push_back(b[i]);
}
while(y < wut.size()) {
ans.push_back(wow[y-1]);
y++;
}
y = 0;
for(int i = 0; i < a.size(); i++) {
if(y < ans.size() && ans[y] == a[i]) {
y++;
}
}
if(y < ans.size()) {
return {-1};
}
y = 0;
for(int i = 0; i < b.size(); i++) {
if(y < ans.size() && ans[y] == b[i]) {
y++;
}
}
if(y < ans.size()) {
return {-1};
}
for(int i = ans.size()-1; i >= 0; i--) {
int z = ans[i];
int x = pos1[z][pos1[z].size()-1],y = pos2[z][pos2[z].size()-1];
if(calc(x) <= y) {
return {-1};
}
x = pos1[z][0]+1;
y = pos2[z][0]+1;
upd(x,y);
}
return ans;
}
