#include<bits/stdc++.h>
using namespace std;
bool czy(int mid,vector<int> &A,vector<int> &B,int N)
{
int p = B.size()-1;
long long wyn =0;
for(int i = 0;i < A.size();++i)
{
while(A[i]+B[p] > mid)
{
if(p == -1)
{
break;
}
p--;
if(p == -1)
{
break;
}
}
wyn += p+1;
}
if(wyn >= N)
{
return 1;
}
return 0;
}
void czy1(int mid,vector<int> &A,vector<int> &B,int N,vector<int> &wyn123)
{
int p = B.size()-1;
for(int i = 0;i < A.size();++i)
{
while(A[i]+B[p] > mid)
{
if(p == -1)
{
break;
}
p--;
if(p == -1)
{
break;
}
}
for(int j = 0;j <= p;++j)
{
wyn123.push_back(A[i]+B[j]);
}
}
sort(wyn123.begin(),wyn123.end());
}
vector <int> smallest_sums (int N, vector <int> A, vector <int> B)
{
long long l = 0,p = 2*(1e9),mid;
vector<int> wyn;
vector<int> wyn1;
while(l < p)
{
mid = (l+p)/2;
if(czy(mid,A,B,N))
{
p = mid;
}
else
{
l = mid+1;
}
}
//cout << l;
czy1(l-1,A,B,N,wyn);
for(int i = 0;i < N;++i)
{
if(wyn.size() <= i)
{
wyn1.push_back(l);
}
else
wyn1.push_back(wyn[i]);
}
return wyn1;
}
/*int main()
{
vector <int> B;
int N,n,x;
vector <int> A;
cin >> N;
cin >> n;
for(int i = 0;i < n;++i)
{
cin >> x;
A.push_back(x);
}
for(int i = 0;i < n;++i)
{
cin >> x;
B.push_back(x);
}
long long l = 0,p = 2*(1e9),mid;
vector<int> wyn;
while(l < p)
{
mid = (l+p)/2;
if(czy(mid,A,B,N))
{
p = mid;
}
else
{
l = mid+1;
}
}
//cout << l;
wyn = czy1(l,A,B,N);
//cout << wyn.size();
for(int i = 0;i < N;++i)
{
cout << wyn[i] << ' ';
}
}*/
