#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int INF = 1e9;
struct SegTree {
vector<int> tree;
int n;
SegTree(int size) {
n = size;
tree.assign(4 * n + 100, INF);
}
void update(int node, int start, int end, int idx, int val) {
if(start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if(idx <= mid) update(2 * node, start, mid, idx, val);
else update(2 * node + 1, mid + 1, end, idx, val);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
int query_all() {
return tree[1];
}
};
vector<int> ucs(vector<int> A, vector<int> B) {
int n = A.size();
int m = B.size();
int max_v = 0;
for(int v : A) max_v = max(max_v, v);
for(int v : B) max_v = max(max_v, v);
vector<vector<int>> posA(max_v + 1);
vector<vector<int>> posB(max_v + 1);
vector<int> ptrA(max_v + 1, 0);
vector<int> ptrB(max_v + 1, 0);
vector<int> k_val(max_v + 1, 0);
vector<bool> is_cand(max_v + 1, false);
vector<bool> in_affected(max_v + 1, false);
for(int i = 0; i < n; ++i) posA[A[i]].push_back(i);
for(int j = 0; j < m; ++j) posB[B[j]].push_back(j);
long long L = 0;
SegTree stA(max_v + 1), stB(max_v + 1);
for(int x = 0; x <= max_v; ++x) {
k_val[x] = min(posA[x].size(), posB[x].size());
L += k_val[x];
if (k_val[x] > 0) {
stA.update(1, 0, max_v, x, posA[x][posA[x].size() - k_val[x]]);
stB.update(1, 0, max_v, x, posB[x][posB[x].size() - k_val[x]]);
}
}
if (L == 0) return {};
auto nextA = [&](int y) {
if (y <= max_v && ptrA[y] < posA[y].size()) return posA[y][ptrA[y]];
return INF;
};
auto nextB = [&](int y) {
if (y <= max_v && ptrB[y] < posB[y].size()) return posB[y][ptrB[y]];
return INF;
};
int limitA = min(stA.query_all(), n - 1);
int limitB = min(stB.query_all(), m - 1);
vector<int> affected;
auto add_affected = [&](int y) {
if (!in_affected[y]) {
affected.push_back(y);
in_affected[y] = true;
}
};
for(int i = 0; i <= limitA; ++i) {
if (nextA(A[i]) == i) add_affected(A[i]);
}
for(int j = 0; j <= limitB; ++j) {
if (nextB(B[j]) == j) add_affected(B[j]);
}
int num_cands = 0;
vector<int> cand_list;
auto check = [&](int y) {
bool valid = (k_val[y] > 0) && (nextA(y) <= limitA) && (nextB(y) <= limitB);
if (valid != is_cand[y]) {
is_cand[y] = valid;
if (valid) {
num_cands++;
cand_list.push_back(y);
} else {
num_cands--;
}
}
};
for(int y : affected) check(y);
for(int y : affected) in_affected[y] = false;
affected.clear();
auto get_cand = [&]() {
while(!cand_list.empty()) {
int y = cand_list.back();
if (is_cand[y]) return y;
cand_list.pop_back();
}
return -1;
};
vector<int> U;
int pA = 0, pB = 0;
int old_limitA = limitA, old_limitB = limitB;
while(L > 0) {
if (num_cands != 1) return {-1};
int x = get_cand();
U.push_back(x);
int new_pA = nextA(x) + 1;
int new_pB = nextB(x) + 1;
k_val[x]--;
L--;
if (k_val[x] == 0) {
stA.update(1, 0, max_v, x, INF);
stB.update(1, 0, max_v, x, INF);
} else {
stA.update(1, 0, max_v, x, posA[x][posA[x].size() - k_val[x]]);
stB.update(1, 0, max_v, x, posB[x][posB[x].size() - k_val[x]]);
}
limitA = min(stA.query_all(), n - 1);
limitB = min(stB.query_all(), m - 1);
for(int i = pA; i < new_pA; ++i) {
if (nextA(A[i]) == i) { ptrA[A[i]]++; add_affected(A[i]); }
}
for(int j = pB; j < new_pB; ++j) {
if (nextB(B[j]) == j) { ptrB[B[j]]++; add_affected(B[j]); }
}
for(int i = max(new_pA, old_limitA + 1); i <= limitA; ++i) {
if (nextA(A[i]) == i) add_affected(A[i]);
}
for(int j = max(new_pB, old_limitB + 1); j <= limitB; ++j) {
if (nextB(B[j]) == j) add_affected(B[j]);
}
pA = new_pA; pB = new_pB;
old_limitA = limitA; old_limitB = limitB;
for(int y : affected) check(y);
for(int y : affected) in_affected[y] = false;
affected.clear();
}
return U;
}
