#include <bits/stdc++.h>
#include <vector>
#include "hieroglyphs.h"
using namespace std;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T> bool cmax(T& x, T y) {
if (y > x) {
x = y;
return true;
}
return false;
};
template<typename T> bool cmin(T& x, T y) {
if (y < x) {
x = y;
return true;
}
return false;
}
constexpr int MAX = int(2e5) + 1;
vector<int> find_boundaries(vector<int> a, vector<int> b) {
int n = int(a.size()), m = int(b.size());
vector<int> occ_diff(MAX);
for (auto x : a) occ_diff[x]++;
for (auto x : b) occ_diff[x]--;
vector<bool> mine(MAX);
for (int i = 0; i < MAX; ++i) {
if (occ_diff[i] <= 0) mine[i] = true;
}
vector<vector<int>> pos(MAX);
for (int i = 0; i < m; ++i) pos[b[i]].push_back(i);
vector<int> first_sub(n, m + 1);
for (int i = 0; i < n; ++i) {
if(!mine[a[i]]) continue;
auto& v = pos[a[i]];
int len = int(v.size());
int x = m + 1;
int j = i - 1;
for (j = i - 1; j >= 0; --j) {
cmin(x, first_sub[j]);
if (a[i] == a[j]) break;
}
if (j == -1) x = -1;
int next_ind = int(lower_bound(v.begin(), v.end(), x + 1) - v.begin());
assert(next_ind < len);
first_sub[i] = v[next_ind];
}
vector<bool> after_me(MAX);
vector<int> previous_to(n, m + 1);
for (int i = n - 1; i >= 0; --i) {
if (!mine[a[i]]) after_me[a[i]] = true;
else {
int j = first_sub[i];
while (j < m && !(after_me[b[j]] && pos[b[j]].back() == j)) ++j;
previous_to[i] = j;
}
}
return previous_to;
}
std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
int N = int(A.size()), M = int(B.size());
vector<int> occ_A(MAX), occ_B(MAX);
debug(A, B);
for (auto x : A) occ_A[x]++;
for (auto x : B) occ_B[x]++;
int req_len = 0;
for (int i = 0; i < MAX; ++i) {
req_len += min(occ_A[i], occ_B[i]);
}
auto previous_to_A = find_boundaries(A, B);
auto previous_to_B = find_boundaries(B, A);
debug(previous_to_A);
debug(previous_to_B);
vector<vector<int>> longest(N + 1, vector<int>(M + 1));
vector<vector<int>> from(N + 1, vector<int>(M + 1, -1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (A[i] == B[j] && previous_to_A[i] > j && previous_to_B[j] > i && cmax(longest[i + 1][j + 1], longest[i][j] + 1)) {
from[i + 1][j + 1] = 3;
}
if (cmax(longest[i + 1][j], longest[i][j])) {
from[i + 1][j] = 1;
}
if (cmax(longest[i][j + 1], longest[i][j])) {
from[i][j + 1] = 2;
}
}
}
if (req_len != longest[N][M]) {
return {-1};
} else {
vector<int> ans;
{
int i = N, j = M;
while (int(ans.size()) < req_len) {
int to = from[i][j];
i -= to & 1;
j -= (to >> 1) & 1;
if (to == 3) {
ans.push_back(A[i]);
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
}
