#include "aplusb.h"
#include <queue>
#define NMAX 100000
int *A, *B;
int sum(int p[2]) {return A[p[0]] + B[p[1]];}
int pair[2*NMAX][2];
struct compareSum {
bool operator() (int below, int above) {
return sum(pair[below]) > sum(pair[above]);
}
};
std::vector<int> smallest_sums(int N, std::vector<int> vectorA, std::vector<int> vectorB) {
A = vectorA.data();
B = vectorB.data();
for (int i = 0; i != N-1; ++i) pair[i][0] = N-1 - i;
for (int i = N; i != 2*N - 1; ++i) pair[i][1] = i - N+1;
std::vector<int> result(N);
std::priority_queue<int, std::vector<int>, compareSum> next;
next.push(N - 1);
int idx = 0;
while (true) {
int node = next.top();
next.pop();
result[idx++] = sum(pair[node]);
if (idx == N) break;
if (node < 2 || pair[node - 1][1] == pair[node - 2][1]) next.push(node - 1);
if (node > 2*N - 4 || pair[node + 1][0] == pair[node + 2][0]) next.push(node + 1);
++pair[node][0];
++pair[node][1];
}
return result;
}
