問題文
長さ N の整数列 A0,A1,…,AN−1 と長さ M の整数列 B0,B1,…,BM−1 が与えられます.ここで A0,A1,…,AN−1 は上に凸です.すなわち
Ai+1−Ai≥Ai+2−Ai+1(0≤i≤N−3)
をみたします.以下の式で定まる長さ N+M−1 の整数列 C0,C1,…,CN+M−2 を求めてください.
Ck=min{Ai+Bj∣i+j=k}(k=0,1,…,N+M−2)
制約
- 1≤N,M≤2×105
- ∣Ai∣≤1018(i=0,1,…,N−1)
- ∣Bj∣≤1018(j=0,1,…,M−1)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます.
出力
長さ N+M−1 の整数列 C0,C1,…,CN+M−2 を半角空白区切りで一行に出力してください.
最後に改行してください.
サンプル
入力1
8 9
-1 4 6 7 7 5 3 -2
3 1 4 1 5 9 2 6 5
出力1
2 0 3 0 4 7 1 1 -1 2 -1 3 5 0 4 3
例えば
C2=min{A0+B2,A1+B1,A2+B0}=min{3,5,9}=3
などとなります.