#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ucs(vector<int> A, vector<int> B) {
int N = A.size(), M = B.size();
// Map value -> list of positions in B (1-indexed for Fenwick tree)
unordered_map<int, vector<int>> posB;
for (int i = 0; i < M; i++)
posB[B[i]].push_back(i + 1);
vector<int> seq;
for (int i = N - 1; i >= 0; i--) {
auto it = posB.find(A[i]);
if (it != posB.end()) {
const vector<int>& positions = it->second;
for (int j = (int)positions.size() - 1; j >= 0; --j) {
seq.push_back(positions[j]);
}
}
}
reverse(seq.begin(), seq.end());
if (seq.empty()) return {};
// Fenwick tree for LIS
int max_val = M + 2;
vector<int> dp(max_val, 0), count(max_val, 0);
int best_len = 0, best_cnt = 0;
unordered_map<int, pair<int, int>> last;
for (int val : seq) {
int mx = 0, cnt = 1;
for (int x = val - 1; x > 0; x -= x & -x)
if (dp[x] > mx) {
mx = dp[x];
cnt = count[x];
} else if (dp[x] == mx) {
cnt += count[x];
}
int new_len = mx + 1;
for (int x = val; x < max_val; x += x & -x) {
if (dp[x] < new_len) {
dp[x] = new_len;
count[x] = cnt;
} else if (dp[x] == new_len) {
count[x] += cnt;
}
}
last[val] = {new_len, cnt};
if (new_len > best_len) {
best_len = new_len;
best_cnt = cnt;
} else if (new_len == best_len) {
best_cnt += cnt;
}
}
if (best_cnt > 1) return {-1};
// Reconstruct the unique LIS (UCS)
vector<int> ucs_sequence;
int len = best_len;
int last_pos = max_val;
for (int i = seq.size() - 1; i >= 0; i--) {
int val = seq[i];
if (val < last_pos && last[val].first == len) {
ucs_sequence.push_back(val);
last_pos = val;
len--;
}
}
reverse(ucs_sequence.begin(), ucs_sequence.end());
// Convert positions back to actual values in B
vector<int> res;
unordered_map<int, queue<int>> val_to_pos;
for (int i = 0; i < M; ++i)
val_to_pos[B[i]].push(i);
for (int a : A) {
if (!ucs_sequence.empty() && !val_to_pos[a].empty() && val_to_pos[a].front() + 1 == ucs_sequence[0]) {
res.push_back(a);
ucs_sequence.erase(ucs_sequence.begin());
}
}
return res;
}
