T837806 雪球增重（drift）

题目描述

一条无限长的直线上铺满了雪。直线上放着 $N$ 个雪球，从左到右编号为 $1\sim N$，初始位置依次为 $X_1,X_2,\ldots,X_N$，且 $X_1<X_2<\cdots<X_N$。所有雪球的初始重量均为 $0$。

接下来有 $Q$ 天会刮风。第 $j$ 天，所有雪球同时以相同的速度移动 $W_j$ 个单位：若 $W_j>0$，则向右移动 $W_j$ 个单位；若 $W_j<0$，则向左移动 $-W_j$ 个单位；若 $W_j=0$，则不移动。雪球的位置关系不会改变，重量也不会影响移动速度。

雪球滚过一段尚未被收走的雪地时，会收走这段雪。每收走长度为 $1$ 的雪，雪球重量就增加 $1$。每段雪只能被最先经过它的雪球收走，已经收走的雪不会重新出现。因此，雪球再次经过一段已无雪的地方时，重量不会增加。

请你求出 $Q$ 天后每个雪球的重量。

输入格式

第一行包含一个整数 $T$，表示数据组数。接下来依次给出每组数据。

每组数据的第一行包含两个整数 $N,Q$。

第二行包含 $N$ 个整数 $X_1,X_2,\ldots,X_N$，表示各雪球的初始位置。

接下来 $Q$ 行，第 $j$ 行包含一个整数 $W_j$，表示第 $j$ 天每个雪球的位移。

输出格式

对于每组数据，依次输出 $N$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个雪球的最终重量。相邻两组数据的输出之间不要添加空行。

输入输出样例 #1

输入 #1

1
4 3
-2 3 5 8
2
-4
7

输出 #1

5
4
2
6

说明/提示

样例解释：

第一天，所有雪球向右移动 $2$ 个单位，重量依次变为 $2,2,2,2$。

第二天，所有雪球向左移动 $4$ 个单位，其中一部分路段已经没有雪。四个雪球新收走的雪的长度依次为 $2,2,0,1$，重量变为 $4,4,2,3$。

第三天，所有雪球向右移动 $7$ 个单位，新收走的雪的长度依次为 $1,0,0,3$，最终重量为 $5,4,2,6$。

样例 2

见 考生目录/drift/drift2.in 与 考生目录/drift/drift2.ans。该样例满足测试点 $1\sim7$ 的约束。

样例 3

见 考生目录/drift/drift3.in 与 考生目录/drift/drift3.ans。该样例满足测试点 $8\sim20$ 的约束。

样例 4

见 考生目录/drift/drift4.in 与 考生目录/drift/drift4.ans。该样例满足测试点 $8\sim20$ 的约束。

样例 5

见 考生目录/drift/drift5.in 与 考生目录/drift/drift5.ans。该样例满足测试点 $8\sim20$ 的约束。

样例 6

见 考生目录/drift/drift6.in 与 考生目录/drift/drift6.ans。该样例满足测试点 $8\sim20$ 的约束。

数据范围

对于所有数据，保证：

• $1\le T\le10$；
• 每组数据中，$1\le N,Q\le2\times10^5$；
• $-10^{12}\le X_i,W_j\le10^{12}$，且 $X_1<X_2<\cdots<X_N$；
• 同一输入文件中，所有数据的 $N$ 之和、$Q$ 之和分别不超过 $4\times10^5$；
• 所有输入的数均为整数。