#include "hieroglyphs.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<int> pos1[200001];
vector<int> pos2[200001];
int dude(int x, int a) {
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) {
int br1 = 0,br2 = 0;
for(int i = 0; i < a.size()-1; i++) {
if(a[i] != a[i+1]) {
br1++;
}
}
for(int i = 0; i < b.size()-1; i++) {
if(b[i] != b[i+1]) {
br2++;
}
}
if(br1 == br2 && a[0] != b[0]) {
return {-1};
}
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);
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++;
}
return ans;
}
