#include <bits/stdc++.h>
using namespace std;
const int cap = 2e5+1;
const int half_cap = 500;
int n, m, block_size, cnt[cap];
vector<set<int>> find_floor_a (cap, set<int>()), find_ceil_a(cap, set<int>()), find_floor_b(cap, set<int>()), find_ceil_b(cap, set<int>());
pair<int, int> pre_block_a[half_cap][cap], pre_block_b[cap][half_cap];
vector<int> a, b;
int check(int la, int ra, int lb, int rb) {
int LA = ceil((double)la/block_size)*block_size, LB = ceil((double)lb/block_size)*block_size,
RA = floor((double)ra/block_size)*block_size, RB = floor((double)rb/block_size)*block_size;
// /* debug */ cout << la << " " << ra << " " << lb << " " << rb << "\n";
// check b to block a
for (int i = LA/block_size; i < RA/block_size; i++) {
pair<int, int> test = {pre_block_a[i][rb].first - pre_block_a[i][lb].first, pre_block_a[i][rb].second};
if (test.first) return test.second;
}
// check a to block b
for (int j = LB/block_size; j < RB/block_size; j++) {
pair<int, int> test = {pre_block_b[ra][j].first - pre_block_b[la][j].first, pre_block_b[ra][j].second};
if (test.first) return test.second;
}
if (LA > RA) LA = RA = la;
if (LB > RB) LB = RB = lb;
for (int i = la; i < LA; i++) cnt[a[i]]++;
for (int i = RA; i < ra; i++) cnt[a[i]]++;
int ans = -1;
for (int j = lb; j < LB; j++) if (cnt[b[j]]) ans = b[j];
for (int j = RB; j < rb; j++) if (cnt[b[j]]) ans = b[j];
for (int i = la; i < LA; i++) cnt[a[i]]--;
for (int i = RA; i < ra; i++) cnt[a[i]]--;
return ans;
}
int find_ceil(int l, int r, int x, bool is_A) {
if (is_A) {
return -*find_ceil_a[x].upper_bound(-r);
}
return -*find_ceil_b[x].upper_bound(-r);
}
int find_floor(int l, int r, int x, bool is_A) {
if (is_A) {
return *find_floor_a[x].lower_bound(l);
}
return *find_floor_b[x].lower_bound(l);
}
vector<int> solve() {
stack<int> ans;
stack<pair<int, int>> S;
S.push({-1, -1});
pair<int, int> top = {n, m};
while (!S.empty()) {
pair<int, int> p = S.top();
int la = p.first, lb = p.second, ra = top.first, rb = top.second;
int x = check(la+1, ra, lb+1, rb);
// /* debug */ cout << x << "\n";
if (x == -1) {
S.pop();
if (!S.empty()){
// x = a[la] = b[lb];
int x = a[la];
top = {find_ceil(la, ra, x, 1), find_ceil(lb, rb, x, 0)};
ans.push(x);
}
} else {
S.push({find_floor(la+1, ra, x, 1), find_floor(lb+1, rb, x, 0)});
}
}
vector<int> out; while (!ans.empty()) {
out.push_back(ans.top()); ans.pop();
}
return out;
}
vector<int> ucs(vector<int> A, vector<int> B) {
a = A; b = B;
n = a.size(), m = b.size();
block_size = sqrt(n);
// /* debug */ cout << "block_size: " << block_size << "\n";
for (int i = 0; i < n; i++) {
find_floor_a[a[i]].insert(i);
find_ceil_a[a[i]].insert(-i);
}
for (int i = 0; i < m; i++) {
find_floor_b[b[i]].insert(i);
find_ceil_b[b[i]].insert(-i);
}
// pre-compute
for (int i = 0; i < n/block_size; i++) {
pre_block_a[i][0] = {0, 0};
for (int i0 = 0; i0 < block_size; i0++) cnt[a[i*block_size + i0]]++;
for (int j = 0; j < m; j++) {
if (cnt[b[j]]) pre_block_a[i][j+1] = {pre_block_a[i][j].first+1, b[j]};
else pre_block_a[i][j+1] = pre_block_a[i][j];
}
for (int i0 = 0; i0 < block_size; i0++) cnt[a[i*block_size + i0]]--;
}
for (int j = 0; j < m/block_size; j++) {
pre_block_b[0][j] = {0, 0};
for (int j0 = 0; j0 < block_size; j0++) cnt[b[j*block_size + j0]]++;
for (int i = 0; i < n; i++) {
if (cnt[a[i]]) pre_block_b[i+1][j] = {pre_block_b[i][j].first+1, a[i]};
else pre_block_b[i+1][j] = pre_block_b[i][j];
}
for (int j0 = 0; j0 < block_size; j0++) cnt[b[j*block_size + j0]]--;
}
return solve();
}
/*
signed main() {
vector<int> sample_1 = ucs({0, 0, 1, 0, 1, 2}, {2, 0, 1, 0, 2});
vector<int> sample_2 = ucs({0, 1, 0}, {1, 0, 1});
for (auto i: sample_2) cout << i << " "; cout << "\n";
}
*/
