A - Belt Conveyor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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つずつ行われ、各操作はそれ以前のすべての操作の結果を反映した状態で実行されます。なお、同じ作業台のスイッチが複数回押されることもあります。

すべての操作が終わった後、各作業台に残っている部品の個数をそれぞれ求めてください。

制約

  • 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
  • 1 行目には、作業台の数を表す整数 N と、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各作業台の初期の部品の個数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目から Q 行分にわたって、各操作でスイッチを押す作業台の番号が与えられる。Q = 0 の場合、この部分は存在しない。
  • 2 + j 行目には、j 回目の操作で押す作業台の番号を表す整数 B_j が与えられる。

出力

すべての操作が終わった後の各作業台の部品の個数を、作業台 1 から作業台 N の順にスペース区切りで 1 行で出力せよ。

入力例 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

Score : 266 pts

Problem Statement

Takahashi manages the production line of a factory. The factory has N workstations arranged in a row, numbered 1, 2, \ldots, N from left to right. Initially, workstation i has A_i parts placed on it.

Each workstation has a switch. When the switch of workstation i (1 \leq i \leq N - 1) is pressed, all parts on workstation i are moved by a belt conveyor to the adjacent workstation i + 1. The moved parts are added to the parts already on workstation i + 1, and the number of parts on workstation i becomes 0. On the other hand, when the switch of workstation N is pressed, all parts on workstation N are ejected outside the production line, and the number of parts on workstation N becomes 0. Ejected parts are completely removed from the production line and have no relation to any subsequent operations.

If the switch of a workstation with 0 parts is pressed, nothing happens (the number of parts on that workstation remains 0).

Takahashi will perform a total of Q switch operations. In the j-th operation (1 \leq j \leq Q), he presses the switch of workstation B_j. The operations are performed one at a time in the order j = 1, 2, \ldots, Q, and each operation is executed in the state reflecting the results of all previous operations. Note that the switch of the same workstation may be pressed multiple times.

After all operations are completed, determine the number of parts remaining on each workstation.

Constraints

  • 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)
  • All input values are integers
  • It is guaranteed that at any point during and after the operations, the number of parts on each workstation does not exceed 2 \times 10^{14}

Input

N Q
A_1 A_2 \ldots A_N
B_1
B_2
\vdots
B_Q
  • The first line contains an integer N representing the number of workstations and an integer Q representing the number of operations, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the initial number of parts on each workstation, separated by spaces.
  • The following Q lines give the workstation number whose switch is pressed in each operation. If Q = 0, this part does not exist.
  • The (2 + j)-th line contains an integer B_j representing the workstation number whose switch is pressed in the j-th operation.

Output

Output the number of parts on each workstation after all operations are completed, in order from workstation 1 to workstation N, separated by spaces, on a single line.

Sample Input 1

5 3
3 1 4 1 5
1
3
5

Sample Output 1

0 4 0 5 0

Sample Input 2

4 4
5 3 2 1
1
1
2
3

Sample Output 2

0 0 0 11

Sample Input 3

8 6
10 20 30 40 50 60 70 80
2
4
6
7
8
8

Sample Output 3

10 0 50 0 90 0 0 0

Sample Input 4

10 10
100 200 300 400 500 600 700 800 900 1000
1
2
3
4
5
6
7
8
9
10

Sample Output 4

0 0 0 0 0 0 0 0 0 0

Sample Input 5

1 1
1000000000
1

Sample Output 5

0