#line 1 "verify/yosupo/convolution/max-plus-convolution/min_plus_convolution_convex_arbitrary.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"
#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;
const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))
template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}
template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}
int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}
template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
vector<int> p(SZ(a));
iota(ALL(p),0);
stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
return p;
}
template<class T,size_t D=0>
struct VecBuilder{
array<size_t,D> d;
VecBuilder<T,D+1> operator[](size_t n)const{
VecBuilder<T,D+1> res{};
for(size_t i=0;i<D;i++)res.d[i]=d[i];
res.d[D]=n;
return res;
}
template<size_t I=0>
auto build(const T &x)const{
if constexpr(I+1==D)return vector<T>(d[I],x);
else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
}
auto operator()(const T &x=T())const{
static_assert(D>0);
return build(x);
}
};
template<class T>
inline constexpr VecBuilder<T> VEC{};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "convolution/max-plus-convolution.hpp"
/**
* Author: Teetat T.
* Date: 2024-09-01
* Description: Max Plus Convolution. Find $C[k] = max_{i+j=k}\{A[i] + B[j]\}$.
* Time: $O(N)$.
*/
// SMAWCK algorithm for finding row-wise maxima.
// f(i,j,k) checks if M[i][j] <= M[i][k].
// f(i,j,k) checks if M[i][k] is at least as good as M[i][j].
// higher is better.
template<class F>
vector<int> smawck(const F &f,const vector<int> &rows,const vector<int> &cols){
int n=(int)rows.size(),m=(int)cols.size();
if(max(n,m)<=2){
vector<int> ans(n,-1);
for(int i=0;i<n;i++){
for(int j:cols){
if(ans[i]==-1||f(rows[i],ans[i],j)){
ans[i]=j;
}
}
}
return ans;
}
if(n<m){
// reduce
vector<int> st;
for(int j:cols){
while(true){
if(st.empty()){
st.emplace_back(j);
break;
}else if(f(rows[(int)st.size()-1],st.back(),j)){
st.pop_back();
}else if(st.size()<n){
st.emplace_back(j);
break;
}else{
break;
}
}
}
return smawck(f,rows,st);
}
vector<int> ans(n,-1);
vector<int> new_rows;
for(int i=1;i<n;i+=2){
new_rows.emplace_back(rows[i]);
}
auto res=smawck(f,new_rows,cols);
for(int i=0;i<new_rows.size();i++){
ans[2*i+1]=res[i];
}
for(int i=0,l=0,r=0;i<n;i+=2){
if(i+1==n)r=m;
while(r<m&&cols[r]<=ans[i+1])r++;
ans[i]=cols[l++];
for(;l<r;l++){
if(f(rows[i],ans[i],cols[l])){
ans[i]=cols[l];
}
}
l--;
}
return ans;
}
template<class F>
vector<int> smawck(const F &f,int n,int m){
vector<int> rows(n),cols(m);
iota(rows.begin(),rows.end(),0);
iota(cols.begin(),cols.end(),0);
return smawck(f,rows,cols);
}
// Max Plus Convolution.
// b must be convex, i.e. b[i]-b[i-1]>=b[i+1]-b[i].
template<class T>
vector<T> max_plus_convolution_arbitary_convex(vector<T> a,const vector<T> &b){
if(a.empty()||b.empty())return {};
if((int)b.size()==1){
for(auto &x:a)x+=b[0];
return a;
}
int n=(int)a.size(),m=(int)b.size();
auto f=[&](int i,int j){
return a[j]+b[i-j];
};
auto cmp=[&](int i,int j,int k){
if(i<k)return false;
if(i-j>=m)return true;
return f(i,j)<=f(i,k);
};
auto best=smawck(cmp,n+m-1,n);
vector<T> ans(n+m-1);
for(int i=0;i<n+m-1;i++){
ans[i]=f(i,best[i]);
}
return ans;
}
#line 4 "verify/yosupo/convolution/max-plus-convolution/min_plus_convolution_convex_arbitrary.test.cpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,m;
cin >> n >> m;
vector<int> a(n),b(m);
for(auto &x:a){
cin >> x;
x*=-1;
}
for(auto &x:b){
cin >> x;
x*=-1;
}
auto c=max_plus_convolution_arbitary_convex(b,a);
for(auto x:c){
cout << -x << " ";
}
}
verify/yosupo/convolution/max-plus-convolution/min_plus_convolution_convex_arbitrary.test.cpp