#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
constexpr ll inf = 4e18;
mt19937 mt(time(0));
struct linked_string {
ll c = -1, len = 0;
linked_string *nxt;
linked_string prepend(ll c) {
linked_string nw;
nw.c = c;
nw.nxt = this;
nw.len = len + 1;
return nw;
}
vector<int> get_reversed() {
vector<int> res(0);
get_reversed(res);
return res;
}
void get_reversed(vector<int> &acc) {
if (c == -1) return;
nxt->get_reversed(acc);
acc.push_back(c);
}
};
vector<int> get_lcs(vector<int> &a, vector<int> &b) {
ll n = sz(a), m = sz(b);
vector<vector<linked_string>> dp(n+1, vector<linked_string>(m+1));
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1].prepend(a[i-1]);
else {
if (dp[i-1][j].len > dp[i][j-1].len) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i][j-1];
}
}
}
return dp[n][m].get_reversed();
}
struct node {
node *left = 0, *right = 0;
ll val = 0;
node(ll val) : val(val) { }
};
node *build(ll n, ll def) {
if (n == 1) return new node(def);
node *res = new node(0);
res->left = build((n+1)/2, def);
res->right = build(n/2, def);
return res;
}
node *point_set(node *k, ll tl, ll tr, ll i, ll v) {
if (tl == tr) return new node(v);
node *nw = new node(*k);
ll mid = tl + (tr - tl) / 2;
if (i <= mid) nw->left = point_set(nw->left, tl, mid, i, v);
else nw->right = point_set(nw->right, mid+1, tr, i, v);
return nw;
}
ll point_get(node *k, ll tl, ll tr, ll i) {
if (tl == tr) return k->val;
ll mid = tl + (tr - tl) / 2;
if (i <= mid) return point_get(k->left, tl, mid, i);
else return point_get(k->right, mid+1, tr, i);
}
vector<int> ucs(vector<int> a, vector<int> b) {
ll n = sz(a), m = sz(b);
vector<int> lcs = get_lcs(a, b);
ll k = sz(lcs);
vector<node *> nxt_occ(k+1);
nxt_occ[k] = build(2e5, k+1);
for (ll i = k; i--;) {
nxt_occ[i] = point_set(nxt_occ[i+1], 0, 2e5-1, lcs[i], i+1);
}
vector<vector<ll>> dp(n+1, vector<ll>(m+1));
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
if (a[i-1] == b[j-1]) {
dp[i][j] = point_get(nxt_occ[dp[i-1][j-1]], 0, 2e5-1, a[i-1]);
if (dp[i][j] > k) return {-1};
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return lcs;
}
