#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}


template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;
template<> const Mint Mint::G = Mint(3);

#include "hieroglyphs.h"

#define N_ 201000
int n, m;
int D[3010][3010], U[3010][3010] , U2[3010][3010];
vi G[201000];
vi sub1(vi &A, vi &B){
    per(i,n){
        per(j,m){
            D[i][j]=max(D[i+1][j],D[i][j+1]);
            if(A[i]==B[j])D[i][j]=max(D[i][j],D[i+1][j+1]+1);
        }
    }
    int x=0,y=0;
    vi T;
    while(x<n||y<m){
        if(x<n&&y<m && A[x]==B[y] && D[x][y]==D[x+1][y+1]+1){
            T.pb(A[x]);x++,y++;
            G[T.back()].pb(si(T) - 1);
        }
        else if(x<n && D[x][y]==D[x+1][y]){
            x++;
        }
        else{
            y++;
        }
    }
    rep(i,n){
        rep(j,m){
            U[i+1][j+1] = max(U[i][j+1],U[i+1][j]);
            if(A[i]==B[j]){
                int z = U[i][j];
                int pv = lower_bound(all(G[A[i]]),z) - G[A[i]].begin();
                if(pv == si(G[A[i]])){
                    return {-1};
                }
                else{
                    int x = G[A[i]][pv];
                    U[i+1][j+1] = max(U[i+1][j+1], x+1);
                }
            }
        }
    }
    per(i,n){
        per(j,m){
            U2[i][j] = max(U2[i][j+1],U2[i+1][j]);
            if(A[i]==B[j]){
                int z = U2[i+1][j+1];
                int pv = lower_bound(all(G[A[i]]),si(T)-z) - G[A[i]].begin();
                pv--;
                if(pv < 0){
                    return {-1};
                }
                else{
                    int x = G[A[i]][pv];
                    U2[i][j] = max(U2[i][j], si(T)-x);
                }
            }
        }
    }
    rng(i,0,n){
        rng(j,0,m){
            if(U[i][j] + U2[i][j] > si(T))return {-1};
            /*if(A[i]==B[j]){
                if(U[i][j] + U2[i+1][j+1] >= si(T))return {-1};
            }*/
        }
    }
    return T;
}
bool Inter(vc<array<int,3>> X, vc<array<int,3>> Y){
    sort(all(X));
    vc<vi>Y1(N_), Y2(N_);
    for(auto &[y, bx, ex]: Y){
        Y1[bx].pb(y);
        Y2[ex].pb(y);
    }
    set<int>Set;
    int pv=0;
    rep(i,N_){
        for(auto &y: Y1[i])Set.insert(y);
        for(auto &y: Y2[i])Set.erase(y);
        while(pv < si(X) && X[pv][0] == i){
            auto it = Set.lower_bound(X[pv][1]);
            if(it != Set.end() && *it < X[pv][2]){
                return true;
            }
            pv++;
        }
    }
    return false;
}
int CKA[N_], CKB[N_], RA[N_], RB[N_], OrdA[N_], OrdB[N_];
std::vector<int> ucs(std::vector<int> A, std::vector<int> B){
    n=si(A);
    m=si(B);
    if(n<=3000 && m<=3000){
        return sub1(A, B);
    }
    vc<vi>GA(201000), GB(201000);
    map<pii,array<int,3> >Map, Map2;
    rep(i,n){
        GA[A[i]].pb(i+1);
        OrdA[i+1] = si(GA[A[i]]);
    }
    rep(i,m){
        GB[B[i]].pb(i+1);
        OrdB[i+1] = si(GB[B[i]]);
    }
    RA[n+1]=n+1;
    RB[m+1]=m+1;
    int sum=0;
    vc<array<int,3>>SegX, SegY;
    rng(i,0,200000){
        if(si(GA[i]) && si(GB[i])){
            sum +=min(si(GA[i]),si(GB[i]));
            if(si(GA[i]) <= si(GB[i])){
                rep(j,si(GA[i])){
                    int a = GA[i][j];
                    CKA[a]=1, RA[a]=a;
                    SegX.pb({a, GB[i][j], GB[i][si(GB[i]) - si(GA[i]) + j]});
                }
            }
            else{
                rep(j,si(GB[i])){
                    int b = GB[i][j];
                    CKB[b]=1, RB[b]=b;
                    SegY.pb({b, GA[i][j], GA[i][si(GA[i]) - si(GB[i]) + j]});
                }
            }
        }
    }
    vi imp = {-1};

    if(!sum){
        vi res;
        return res;
    }
    if(Inter(SegX, SegY)){
        return imp;
    }
    gnr(i,n,1){
        if(RA[i]!=i)RA[i]=RA[i+1];
    }
    gnr(i,m,1){
        if(RB[i]!=i)RB[i]=RB[i+1];
    }
    Map[{0,0}] = {0,-1,-1};
    int xx=-1,yy=-1;
    int cc=0;
    while(!Map.empty()){
        cc++;
        if(si(Map) + cc > 2e6){
            return {-1};
        }
        auto [z,c] = *Map.begin();
        Map2[z]=c;
        auto [x,y] = z;
        if(c[0]==sum){
            xx = x,yy=y;
        }
        int t = RA[x+1];
        if(t<=n){
            int ch = A[t-1];
            int pv = lower_bound(all(GB[ch]),y+1)-GB[ch].begin();
            if(pv < si(GB[ch])){
                if(si(GB[ch])-pv >= si(GA[ch]) - OrdA[t]){
                    pii tp = {t, GB[ch][pv]};
                    if(!Map.count(tp) || Map[tp][0]<=c[0]){
                        Map[tp]={c[0]+1, x,y};
                    }
                }
            }
        }
        t = RB[y+1];
        if(t<=m){
            int ch = B[t-1];
            int pv = lower_bound(all(GA[ch]),x+1)-GA[ch].begin();
            if(pv < si(GA[ch])){
                if(si(GA[ch])-pv >= si(GB[ch]) - OrdB[t]){
                    pii tp = {GA[ch][pv], t};
                    if(!Map.count(tp) || Map[tp][0]<=c[0]){
                        Map[tp]={c[0]+1, x,y};
                    }
                }
            }
        }
        Map.erase(Map.begin());
    }
    if(xx==-1 && yy==-1){
        return imp;
    }
    Map = Map2;
    vi res;
    while(xx){
        res.pb(A[xx-1]);
        auto [t,nx,ny] = Map[{xx,yy}];
        xx=nx,yy=ny;
    }
    reverse(all(res));
    int ck=0;
    rng(i,0,200000){
        if(si(GA[i])+si(GB[i])>3)ck=1;
    }
    return res;
}