[JOI 2021 Final] 雪玉
题目描述
在一条无限长的数轴上,有 $N$ 个雪球,这 $N$ 个雪球编号为 $1 \sim N$,第 $i$ 个雪球在第 $A_i$ 个点上。刚开始,整条数轴覆盖满了雪,接下来 $Q$ 天将会刮起大风,第 $j$ 天的风力强度为 $W_j$,如果 $W_j$ 为正数,所有雪球都朝右移动 $W_j$ 个单位长度,如果 $W_j$ 为负数,所有雪球都朝左移动 $-W_j$ 个单位长度。
当一个区间 $[a,a+1]$ 被雪覆盖时,雪球滚上去雪球的质量会加一,这一个区间里的雪也会被清空。刚开始每一个雪球的质量均为 $0$,而这 $Q$ 天里也没有再下雪。
你想问这 $Q$ 天结束后每个雪球的质量是怎样的。
输入输出格式
输入格式
第一行两个整数 $N,Q$ 代表雪球个数和下雪天数。
第二行 $N$ 个整数 $A_i$ 代表这 $N$ 个雪球的初始位置。
接下来 $Q$ 行每行一个整数 $W_j$ 代表每一天的风力强度。
输出格式
$N$ 行每行一个整数代表这 $Q$ 天结束后每一个雪球的质量。
输入输出样例
输入样例 #1
4 3
-2 3 5 8
2
-4
7
输出样例 #1
5
4
2
6
输入样例 #2
1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000
输出样例 #2
3000000000000
输入样例 #3
10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6
输出样例 #3
14
8
7
9
11
10
9
8
5
10
说明
#### 样例 1 解释
雪球初始位置为 $-2,3,5,8$,初始质量为 $0,0,0,0$。
- 第一天过后,雪球位置为 $0,5,7,10$,质量为 $2,2,2,2$。
- 第二天过后,雪球位置为 $-4,1,3,6$,质量为 $4,4,2,3$。
- 第三天过后,雪球位置为 $3,8,10,13$,质量为 $5,4,2,6$。
#### 数据规模与约定
**本题采用捆绑测试。**
- Subtask 1(33 pts):$N,Q \le 2000$。
- Subtask 2(67 pts):无特殊限制。
对于 $100\%$ 的数据,$1 \le N,Q \le 2 \times 10^5$,$|A_i|,|W_j| \le 10^{12}$,$A_i<A_{i+1}$。
#### 说明
翻译自 [The 20th Japanese Olympiad in Informatics Final Round B 雪玉的英文翻译 Snowball](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t2-en.pdf)。