#include <bits/stdc++.h>
#include "hieroglyphs.h"
using namespace std;
class segtree {
public:
struct node {
int min_val = INT_MAX;
void apply(int l, int r, int v) {
min_val = v;
}
};
node unite(const node &a, const node &b) const {
node res;
res.min_val = min(a.min_val, b.min_val);
return res;
}
inline void push(int x, int l, int r) {
}
inline void pull(int x, int z) {
tree[x] = unite(tree[x + 1], tree[z]);
}
int n;
vector<node> tree;
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
pull(x, z);
}
template <typename M, typename... T>
void build(int x, int l, int r, const vector<M> &v, const T&... t) {
if (l == r) {
tree[x].apply(l, r, v[l], t...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v, t...);
build(z, y + 1, r, v, t...);
pull(x, z);
}
template <typename M, typename... T>
segtree(const vector<M> &v, const T&... t) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v, t...);
}
segtree(int _n) : n(_n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
segtree(){};
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
node res{};
if (rr <= y) {
res = get(x + 1, l, y, ll, rr);
} else {
if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
node get(int p) {
assert(0 <= p && p <= n - 1);
return get(0, 0, n - 1, p, p);
}
template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v...);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}
template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v...);
}
};
vector<int> ucs (vector<int> a, vector<int> b) {
int n = a.size();
int m = b.size();
int Total_number = max(*max_element(a.begin(), a.end()), *max_element(b.begin(), b.end())) + 1;
vector<vector<int>> A_postions_of_num(Total_number, vector<int>(1, -1));
vector<vector<int>> B_postions_of_num(Total_number, vector<int>(1, -1));
for (int i = 0; i < n; i++) {
A_postions_of_num[a[i]].push_back(i);
}
for (int i = 0; i < m; i++) {
B_postions_of_num[b[i]].push_back(i);
}
for (int i = 0; i < Total_number; i++) {
A_postions_of_num[i].push_back(n);
B_postions_of_num[i].push_back(m);
}
auto Nearest_next_B = [&](int pos, int val, int dir) {
if (pos == m && dir == +1) return m;
if (pos == -1 && dir == -1) return -1;
auto it = lower_bound(B_postions_of_num[val].begin(), B_postions_of_num[val].end(), pos);
if (dir == +1) {
assert(it != B_postions_of_num[val].end());
if (*it == pos) {
assert(next(it) != B_postions_of_num[val].end());
it++;
return *it;
} else {
return *it;
}
} else {
assert(it != B_postions_of_num[val].begin());
it--;
return *it;
}
};
auto Nearest_next_A = [&](int pos, int val, int dir) {
if (pos == n && dir == +1) return n;
if (pos == -1 && dir == -1) return -1;
auto it = lower_bound(A_postions_of_num[val].begin(), A_postions_of_num[val].end(), pos);
if (dir == +1) {
assert(it != A_postions_of_num[val].end());
if (*it == pos) {
assert(next(it) != A_postions_of_num[val].end());
it++;
return *it;
} else {
return *it;
}
} else {
assert(it != A_postions_of_num[val].begin());
it--;
return *it;
}
};
vector<int> Left_most_reached_in_B_of_A(n, m);
vector<int> Left_most_reached_in_A_of_B(m, n);
for (int rot = 0; rot < 2; rot++) {
segtree Left_B_reached_from_a(n);
for (int pos_a = 0; pos_a < n; pos_a++) {
int prev_a_same_val = Nearest_next_A(pos_a, a[pos_a], -1);
int prev_b_reached = prev_a_same_val == -1 ? -1 : Left_B_reached_from_a.get(prev_a_same_val).min_val;
if (prev_a_same_val < pos_a - 1) {
prev_b_reached = min(prev_b_reached, Left_B_reached_from_a.get(prev_a_same_val + 1, pos_a - 1).min_val);
}
int cur_b_reached = Nearest_next_B(prev_b_reached, a[pos_a], +1);
Left_B_reached_from_a.modify(pos_a, pos_a, cur_b_reached);
Left_most_reached_in_B_of_A[pos_a] = cur_b_reached;
}
swap(n, m);
swap(a, b);
swap(Left_most_reached_in_B_of_A, Left_most_reached_in_A_of_B);
swap(A_postions_of_num, B_postions_of_num);
}
vector<bool> A_must(n);
vector<bool> B_must(m);
bool matched = true;
for (int num = 0; num < Total_number; num++) {
int A_num_sz = A_postions_of_num[num].size();
int B_num_sz = B_postions_of_num[num].size();
if (A_num_sz >= B_num_sz) {
int cnt = 0;
int B_pos_last_matched = m;
for (int a_pos_id = A_num_sz - 2; a_pos_id >= 1; a_pos_id--) {
int a_pos = A_postions_of_num[num][a_pos_id];
assert(a[a_pos] == num);
int b_far_pos = Left_most_reached_in_B_of_A[a_pos];
if (b_far_pos >= B_pos_last_matched) continue;
int next_B_match = Nearest_next_B(B_pos_last_matched, num, -1);
B_pos_last_matched = next_B_match;
A_must[a_pos] = true;
cnt++;
}
if (cnt != B_num_sz - 2) {
matched = false;
break;
}
}
if (B_num_sz >= A_num_sz) {
int cnt = 0;
int A_pos_last_matched = n;
for (int b_pos_id = B_num_sz - 2; b_pos_id >= 1; b_pos_id--) {
int b_pos = B_postions_of_num[num][b_pos_id];
assert(b[b_pos] == num);
int a_far_pos = Left_most_reached_in_A_of_B[b_pos];
if (a_far_pos >= A_pos_last_matched) continue;
int next_A_match = Nearest_next_A(A_pos_last_matched, num, -1);
A_pos_last_matched = next_A_match;
B_must[b_pos] = true;
cnt++;
}
if (cnt != A_num_sz - 2) {
matched = false;
break;
}
}
if (A_num_sz < B_num_sz) for (int i : A_postions_of_num[num]) if (i > -1 && i < n) A_must[i] = true;
if (B_num_sz < A_num_sz) for (int i : B_postions_of_num[num]) if (i > -1 && i < m) B_must[i] = true;
}
if (!matched) {
return (vector<int>) {-1};
}
vector<int> A_ret_pos = {-1};
vector<int> B_ret_pos = {-1};
for (int i = 0; i < n; i++) if (A_must[i]) A_ret_pos.push_back(i);
for (int i = 0; i < m; i++) if (B_must[i]) B_ret_pos.push_back(i);
A_ret_pos.push_back(n);
B_ret_pos.push_back(m);
assert(A_ret_pos.size() == B_ret_pos.size());
int sz = A_ret_pos.size();
for (int i = 1; i < sz - 1; i++) if (a[A_ret_pos[i]] != b[B_ret_pos[i]]) return (vector<int>) {-1};
vector<int> id_in_A_ret(n);
vector<int> id_in_B_ret(m);
for (int i = 0; i < n; i++) {
id_in_A_ret[i] = A_must[i];
if (i > 0) id_in_A_ret[i] += id_in_A_ret[i - 1];
}
for (int i = 0; i < m; i++) {
id_in_B_ret[i] = B_must[i];
if (i > 0) id_in_B_ret[i] += id_in_B_ret[i - 1];
}
for (int a_pos = 0; a_pos < n; a_pos++) {
if (A_must[a_pos]) continue;
int b_left_pos = Left_most_reached_in_B_of_A[a_pos];
assert(b_left_pos > -1);
if (b_left_pos >= m) continue;
if (id_in_A_ret[a_pos] > id_in_B_ret[b_left_pos]) return (vector<int>) {-1};
}
for (int b_pos = 0; b_pos < m; b_pos++) {
if (B_must[b_pos]) continue;
int a_left_pos = Left_most_reached_in_A_of_B[b_pos];
assert(a_left_pos > -1);
if (a_left_pos >= n) continue;
if (id_in_B_ret[b_pos] > id_in_A_ret[a_left_pos]) return (vector<int>) {-1};
}
vector<int> ret;
for (int i : A_ret_pos) if (i > -1 && i < n) ret.push_back(a[i]);
return ret;
}
