#include <bits/stdc++.h>
#include "aplusb.h"
using namespace std;
#define il long long
int oa[100010], ob[100010];
vector<int> smallest_sums(int n, vector<int> a, vector<int> b)
{
vector<int> ans;
a.insert(a.begin(), 0);
b.insert(b.begin(), 0);
int l = 1, r = n;
int res = -1;
while (l <= r){
int mid = (l+r)/2;
if (mid < n && (n+1)-mid < n){
if (a[mid+1] < b[(n+1)-mid]) l = mid+1;
else if (b[(n+1)-mid+1] < a[mid]) r = mid-1;
else {
res = mid;
break;
}
}
else if (mid == n){
if (b[(n+1)-mid+1] < a[mid]) r = mid-1;
else {
res = mid;
break;
}
}
else if ((n+1)-mid == n){
if (a[mid+1] < b[(n+1)-mid]) l = mid+1;
else {
res = mid;
break;
}
}
}
if (res == -1) res = l;
vector<int> all;
il ll = (il)res;
il rr = (il)(n+1)-res;
while ((ll-1ll) * r >= n && ll * (rr-1ll) >= n){
if (a[ll] > a[rr]) ll--;
else if (a[rr] > a[ll]) rr--;
else if (ll >= rr) ll--;
else rr--;
}
for (int i = 1; i <= ll; i++){
for (int j = 1; j <= rr; j++){
all.push_back({a[i] + b[j]});
}
}
sort(all.begin(), all.end());
for (int i = 0; i < n; i++){
ans.push_back(all[i]);
}
return ans;
}
