题目描述

$Bob$ 有 $n$ 盆植物，每盆植物都有一个初始高度 $a_i$。$n$ 盆植物排成一排，$Bob$ 准备用能量棒照射这 $n$ 盆植物，由于技术原因 $Bob$ 只能站在第一盆植物前，然后拿着能量棒照向第 $n$ 盆，高的植物会挡住矮的植物。

$Bob$ 计划使用 $m$ 次能量棒，第 $i$ 次能覆盖的高度是 $[0,b_i]$，当植物吸收到 $l$ 长度的能力棒照射，会长高 $l$，注意前面高的植物会挡住矮植物，也可能会挡住部分. 如下图：

解释：使用高度为 $6$ 的能量棒照射初始高度为 $3,2,5$ 的 $3$ 盆植物，第二盆完全被遮挡，第三盆吸收高度区间 $[3,5]$ 的能量。照射完之后，第一盆高度变为 $3+3$，第二盆高度为 $2+0$ ，第三盆高度变为 $5+2$。

经过 $m$ 次照射后，$Bob$ 想知道 $n$ 盆植物的高度。

输入格式

第一行两个整数 $n$ 和 $m$

第二行，$n$ 个整数 $a_i$

第三行，$m$ 个整数 $b_i$

输出格式

$n$ 行，每行一个整数，表经过 $m$ 次照射后，第 $i$ 盆植物的高度。

3 2
3 2 5
6 1

7
2
7

样例解释

经过第一次照射 ，$3$ 盆植物高度变为 $6,2,7$ ,见题目图片。

经过第二次照射， $3$ 盆植物高度变为 $7,2,7$

数据规模与约定

所有数据满足：$1 \le n,m \le 2\cdot 10^5$，$1\leq a_i,b_i \leq 10^9$

subtask1: $1\le n,m \le 10^3$，$40$ 分

subtask2: $1 \le n,m \le 2\cdot 10^5$，$60$ 分

注意数据溢出