#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 RA[N_], RB[N_], OrdA[N_], OrdB[N_], PP[N_];
vc<pii> D[N_];

int PR[N_];

const int SZ = (1<<18);

struct Tree{
    set<pii>SetX[SZ+SZ];
    set<pii>SetY[SZ+SZ];
    void Put2(set<pii> &s, pii t){
        s.insert(t);
        auto it = s.find(t);
        auto it2 = it; it2++;
        if(it2!=s.end() && it2->se >= t.se){
            s.erase(it);
            return;
        }
        while(it!=s.begin()){
            it2 = it; it2--;
            if(it2->se > t.se)break;
            s.erase(it2);
        }
    }
    void Put(int a, pii t){
        a += SZ;
        while(a){
            Put2(SetX[a],t);
            Put2(SetY[a],pii(t.se,t.fi));
            a>>=1;
        }
    }
    int Get2(set<pii> &s, int t){
        auto it = s.lower_bound(pii(t,-1));
        if(it == s.end())return -1;
        return it->se;
    }
    int Get(int b, int e, int t, int ck){
        b+=SZ,e+=SZ;
        int r = -1;
        while(b<=e){
            if((b&1)){
                if(ck==0)r = max(r, Get2(SetX[b], t));
                else r = max(r, Get2(SetY[b], t));
            }
            if(!(e&1)){
                if(ck==0)r = max(r, Get2(SetX[e], t));
                else r = max(r, Get2(SetY[e], t));
            }
            b=(b+1)>>1,e=(e-1)>>1;
        }
        return r;
    }
}IT;

vi GA[201000], GB[201000], GG[201000];
int RightA(int a, int x){
    int pv = lower_bound(all(GA[a]),x)-GA[a].begin();
    if(si(GA[a])==pv)return n+1;
    return GA[a][pv];
}
int RightB(int a, int x){
    int pv = lower_bound(all(GB[a]),x)-GB[a].begin();
    if(si(GB[a])==pv)return m+1;
    return GB[a][pv];
}

int LeftA(int a, int x){
    int pv = lower_bound(all(GA[a]),x+1)-GA[a].begin();
    if(!pv)return -1;
    return GA[a][pv-1];
}
int LeftB(int a, int x){
    int pv = lower_bound(all(GB[a]),x+1)-GB[a].begin();
    if(!pv)return -1;
    return GB[a][pv-1];
}

std::vector<int> ucs(std::vector<int> A, std::vector<int> B){
    n=si(A);
    m=si(B);
    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;
    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];
                     RA[a]=a;
                }
            }
            else{
                rep(j,si(GB[i])){
                    int b = GB[i][j];
                    RB[b]=b;
                }
            }
        }
    }
    vi imp = {-1};

    if(!sum){
        vi res;
        return res;
    }
    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(Map2) > 1e6){
            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;
    vc<pii> Z;
    while(xx){
        res.pb(A[xx-1]);
        Z.pb({xx,yy});
        auto [t,nx,ny] = Map[{xx,yy}];
        xx=nx,yy=ny;
    }
    reverse(all(res));
    reverse(all(Z));

    IT.Put(si(res),pii(n+1,m+1));

    rep(i,si(res)){
        GG[res[i]].pb(i);
    }

    per(i,si(res)){
        int t = res[i];
        auto [x,y] =Z[i];
        int e = si(res);
        if(PP[t]) e = PP[t];
        PP[t] = i;

        int t1 = RightA(t, x+1);
        int t2 = RightB(t, y+1);
        if(t1 <= n && t2 <= m){
            if(IT.Get(i+1,e,t1+1,0) > t2){
                return {-1};
            }
        }
        int ny = IT.Get(i+1,e,x+1,0);
        int nx = IT.Get(i+1,e,y+1,1);

        nx = LeftA(t,nx-1);
        ny = LeftB(t,ny-1);

        //printf("%d %d %d %d\n",x,y,nx,ny);

        int ck=0;

        if(nx > x) IT.Put(i, pii(nx,y)), ck=1;
        if(ny > y) IT.Put(i, pii(x,ny)), ck=1;
        if(!ck) IT.Put(i,pii(x,y));

    }
    rng(i,0,200000){
        if(si(GA[i]) && si(GB[i])){
            int x = GA[i][0], y = GB[i][0];
            int pv = GG[i][0];
            if(IT.Get(0,pv,x+1,0)>y)return{-1};
        }
    }

    return res;
}