B - Brightness of Street Lights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は市役所の街灯管理係として働いています。彼が担当する通りには N 個の街灯が一列に並んでおり、左から順に 1, 2, \ldots, N と番号が付けられています。

各街灯 i には初期の明るさを表す整数値 A_i が与えられています。高橋君が街灯 i の整備を行うと、その街灯だけでなく隣接する街灯にも影響が及びます。具体的には、街灯 i-1, i, i+1 のうち番号が 1 以上 N 以下であるものすべての明るさが 1 ずつ増加します。

高橋君は合計で M 回の整備作業を行います。j 回目 (1 \leq j \leq M) の作業では街灯 B_j の整備を行います。なお、同じ街灯に対して複数回整備が行われることもあります。

すべての作業が終わった後の、各街灯の明るさを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq B_j \leq N
  • 入力はすべて整数

入力

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • 1 行目には、街灯の個数を表す整数 N と、整備作業の回数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各街灯の初期の明るさを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各作業で整備を行う街灯の番号を表す整数 B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。

出力

すべての作業が終わった後の各街灯の明るさを、街灯 1 から街灯 N の順にスペース区切りで 1 行で出力せよ。

入力例 1

5 3
1 2 3 4 5
2 4 4

出力例 1

2 3 6 6 7

入力例 2

7 5
0 0 0 0 0 0 0
1 3 5 7 4

出力例 2

1 2 2 3 2 2 1

入力例 3

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

出力例 3

102 203 301 404 503 604 701 801 901 1001

Score : 266 pts

Problem Statement

Takahashi works as a street light manager at the city hall. The street he is responsible for has N street lights arranged in a row, numbered 1, 2, \ldots, N from left to right.

Each street light i is given an integer value A_i representing its initial brightness. When Takahashi performs maintenance on street light i, the effect extends not only to that street light but also to its adjacent street lights. Specifically, the brightness of all street lights among i-1, i, i+1 whose numbers are between 1 and N (inclusive) increases by 1.

Takahashi performs a total of M maintenance operations. In the j-th operation (1 \leq j \leq M), he performs maintenance on street light B_j. Note that the same street light may be maintained multiple times.

Determine the brightness of each street light after all operations are completed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq B_j \leq N
  • All input values are integers

Input

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • The first line contains an integer N representing the number of street lights and an integer M representing the number of maintenance operations, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the initial brightness of each street light, separated by spaces.
  • The third line contains integers B_1, B_2, \ldots, B_M representing the street light numbers to be maintained in each operation, separated by spaces.

Output

Print the brightness of each street light after all operations are completed, in order from street light 1 to street light N, separated by spaces, on a single line.

Sample Input 1

5 3
1 2 3 4 5
2 4 4

Sample Output 1

2 3 6 6 7

Sample Input 2

7 5
0 0 0 0 0 0 0
1 3 5 7 4

Sample Output 2

1 2 2 3 2 2 1

Sample Input 3

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

Sample Output 3

102 203 301 404 503 604 701 801 901 1001