#include "hieroglyphs.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 3005;
ll dp[N][N], best[N][N], realv[N * 2];
ll nxt[N][N * 2];
vector<int> lcs(vector<int> &a, vector<int> &b)
{
ll n = a.size(), m = b.size();
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++)
{
dp[i][j] = max({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + (a[i - 1] == b[j - 1])});
if (dp[i - 1][j] == dp[i][j]) best[i][j] = 0;
else if (dp[i][j - 1] == dp[i][j]) best[i][j] = 1;
else best[i][j] = 2;
}
vector<int> res;
ll i = n, j = m;
while (i > 0 and j > 0)
{
if (best[i][j] == 2) res.push_back(a[i - 1]), i--, j--;
else if (best[i][j] == 1) j--;
else i--;
}
reverse(res.begin(), res.end());
return res;
}
std::vector<int> ucs(std::vector<int> a, std::vector<int> b)
{
ll n = a.size(), m = b.size();
{
map<ll, ll> mp;
for (ll i : a) mp[i] = 1;
for (ll i : b) mp[i] = 1;
ll cnt = 0;
for (auto i : mp) mp[i.first] = ++cnt, realv[cnt] = i.first;
for (int &i : a) i = mp[i];
for (int &i : b) i = mp[i];
}
vector<int> ans = lcs(a, b);
if (ans.empty()) return {};
ll mx = *max_element(ans.begin(), ans.end());
for (ll i = 1; i <= mx; i++) nxt[ans.size()][i] = ans.size() + 1;
for (ll i = ans.size() - 1; i >= 0; i--)
{
for (ll j = 1; j <= mx; j++) nxt[i][j] = nxt[i + 1][j];
nxt[i][ans[i]] = i + 1;
}
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++) dp[i][j] = 0;
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (a[i - 1] == b[j - 1]) dp[i][j] = max(dp[i][j], nxt[dp[i - 1][j - 1]][a[i - 1]]);
if (dp[i][j] > ans.size()) return {-1};
}
for (int &i : ans) i = realv[i];
return ans;
}
