#include "aplusb.h"
#include <algorithm>
using namespace std;
int n;
vector <int> a, b;
bool check(int x) {
int i = 0, j = n - 1, len = 0;
while(i < n && j >= 0 && len < n) {
if(a[i] + b[j] <= x) {
i++;
len += (j + 1);
}
else j--;
}
if(len >= n) return 1;
return 0;
}
vector<int> smallest_sums(int N, vector<int> A, vector<int> B) {
n = N; a = A; b = B;
int p = -1, k = 2e9 + 1, sr = 0;
vector <int> c;
while(p + 1 < k) {
sr = (p + k) / 2;
if(check(sr)) k = sr;
else p = sr;
}
int ost = (p + 1);
for(int i = 0; i < n; i++) {
if((int)c.size() >= n) break;
for(int j = 0; j < n; j++) {
if(a[i] + b[j] < ost) c.push_back(a[i]+b[j]);
else break;
}
}
while((int)c.size() < n) c.push_back(ost);
sort(c.begin(), c.end());
return {c};
}
