分数: 266 分
问题陈述
高桥管理着一家工厂的生产线。工厂有 N 工作站排列成一排,编号 1, 2, \ldots, N 从左到右。最初,工作站 i 有 A_i 零件放置在其上。
每个工作站都有一个交换机。当工作站切换时 i (1 \leq i \leq N - 1) 被按下,所有部件都在工作站上 i 通过皮带输送机移动到相邻的工作站 i + 1。移动的零件将添加到工作站上已有的零件中 i + 1,以及工作站上的零件数量 i 变为 0。另一方面,当工作站切换时 N 被按下,所有部件都在工作站上 N 被弹出生产线外,以及工作站上的零件数量 N 变为 0。弹出的零件完全从生产线上移除,与任何后续操作无关。
如果工作站的交换机带有 0 零件被按下,没有任何反应(该工作站上的零件数量仍然存在) 0).
高桥将总共表演 Q 开关操作。在 j第一次操作 (1 \leq j \leq Q),他按下了工作站的开关 B_j。这些操作按顺序一次执行一个 j = 1, 2, \ldots, Q,并且每个操作都在反映所有先前操作的结果的状态下执行。请注意,同一工作站的开关可能会被按下多次。
所有操作完成后,确定每个工作站上剩余的零件数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq Q \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_j \leq N (1 \leq j \leq Q)
- 所有输入值均为整数
- 保证在操作期间和操作之后的任何时刻,每个工作站上的零件数量不超过 2 \times 10^{14}
输入
N Q A_1 A_2 \ldots A_N B_1 B_2 \vdots B_Q
- 第一行包含一个整数 N 代表工作站数量和一个整数 Q 代表操作次数,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 表示每个工作站上零件的初始数量,以空格分隔。
- 以下 Q 行给出在每次操作中按下开关的工作站编号。如果 Q = 0,这部分不存在。
- 的 (2 + j)- 第行包含一个整数 B_j 代表按下开关的工作站编号 j-第次操作。
输出
所有操作完成后输出每个工作站上的零件数量,按从工作站开始的顺序 1 到工作站 N,用空格分隔,在一行上。
示例输入 1
5 3 3 1 4 1 5 1 3 5
示例输出 1
0 4 0 5 0
示例输入 2
4 4 5 3 2 1 1 1 2 3
示例输出 2
0 0 0 11
示例输入 3
8 6 10 20 30 40 50 60 70 80 2 4 6 7 8 8
示例输出 3
10 0 50 0 90 0 0 0
示例输入 4
10 10 100 200 300 400 500 600 700 800 900 1000 1 2 3 4 5 6 7 8 9 10
示例输出 4
0 0 0 0 0 0 0 0 0 0
示例输入 5
1 1 1000000000 1
示例输出 5
0