A - Waterflow on Stairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君の家の庭には、 N 段の階段状に並んだ植木鉢があります。

それぞれの植木鉢には最初に水が入っており、 i 番目の植木鉢には A_i ミリリットルの水が入っています。階段状に配置されているため、 i 番目の植木鉢は i + 1 番目の植木鉢より高い位置にあります（ N 番目の植木鉢が最も低い位置にあり、その先は排水溝につながっています）。

高橋君が植木鉢に日光を当てると、水の一部が蒸発し、残りが下の段の植木鉢へ流れ落ちる現象が起きます。具体的には、 i 番目の植木鉢に日光を当てると以下のことが起きます：

  • その植木鉢に入っている水のうち B_i ミリリットルが蒸発して消える（水が B_i ミリリットル未満の場合は、すべての水が蒸発する）
  • 蒸発後に残った水はすべて、下の段の植木鉢へ流れ落ちる（ i < N の場合は i + 1 番目の植木鉢へ、 i = N の場合は排水溝へ流れ落ちて消える）

高橋君は Q 回の操作を順番に行います。 j 回目の操作では、 C_j 番目の植木鉢に日光を当てます。

すべての操作が終わった後、各植木鉢に残っている水の量をそれぞれ求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_j \leq N (1 \leq j \leq Q)
  • 入力はすべて整数

入力

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_Q
  • 1 行目には、植木鉢の個数を表す N と、操作の回数を表す Q が、スペース区切りで与えられる。
  • 2 行目には、各植木鉢の初期の水の量を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各植木鉢に日光を当てたときに蒸発する水の量を表す B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。
  • 4 行目には、各操作で日光を当てる植木鉢の番号を表す C_1, C_2, \ldots, C_Q が、スペース区切りで与えられる。

出力

すべての操作が終わった後の、各植木鉢に残っている水の量を、 1 番目から N 番目の順にスペース区切りで 1 行に出力せよ。

入力例 1

3 2
10 5 3
3 2 4
1 2

出力例 1

0 0 13

入力例 2

5 6
100 50 30 20 10
20 10 15 5 8
1 2 3 4 5 1

出力例 2

0 0 0 0 0

入力例 3

7 10
1000000000 500000000 300000000 200000000 100000000 50000000 25000000
100000000 200000000 150000000 80000000 60000000 30000000 20000000
1 1 2 2 3 3 4 5 6 7

出力例 3

0 0 0 0 0 0 0

Score : 266 pts

Problem Statement

In Takahashi's garden, there are flower pots arranged in N steps like a staircase.

Each flower pot initially contains water, and the i-th flower pot contains A_i milliliters of water. Due to the staircase arrangement, the i-th flower pot is positioned higher than the (i + 1)-th flower pot (the N-th flower pot is at the lowest position, and beyond it is a drain).

When Takahashi exposes a flower pot to sunlight, part of the water evaporates and the rest flows down to the flower pot on the step below. Specifically, when sunlight is applied to the i-th flower pot, the following occurs:

  • B_i milliliters of the water in that flower pot evaporates and disappears (if the water is less than B_i milliliters, all the water evaporates)
  • All the water remaining after evaporation flows down to the flower pot on the step below (if i < N, it flows to the (i + 1)-th flower pot; if i = N, it flows into the drain and disappears)

Takahashi performs Q operations in order. In the j-th operation, he exposes the C_j-th flower pot to sunlight.

After all operations are completed, determine the amount of water remaining in each flower pot.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_j \leq N (1 \leq j \leq Q)
  • All inputs are integers

Input

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_Q
  • The first line contains N, the number of flower pots, and Q, the number of operations, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N, the initial amounts of water in each flower pot, separated by spaces.
  • The third line contains B_1, B_2, \ldots, B_N, the amounts of water that evaporate when each flower pot is exposed to sunlight, separated by spaces.
  • The fourth line contains C_1, C_2, \ldots, C_Q, the numbers of the flower pots to be exposed to sunlight in each operation, separated by spaces.

Output

Output the amount of water remaining in each flower pot after all operations are completed, from the 1st to the N-th, separated by spaces on a single line.

Sample Input 1

3 2
10 5 3
3 2 4
1 2

Sample Output 1

0 0 13

Sample Input 2

5 6
100 50 30 20 10
20 10 15 5 8
1 2 3 4 5 1

Sample Output 2

0 0 0 0 0

Sample Input 3

7 10
1000000000 500000000 300000000 200000000 100000000 50000000 25000000
100000000 200000000 150000000 80000000 60000000 30000000 20000000
1 1 2 2 3 3 4 5 6 7

Sample Output 3

0 0 0 0 0 0 0