A - ポイントカードの残高管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君はショッピングモールのポイントカードシステムを管理しています。このモールには N 人の会員がおり、会員 i (1 \leq i \leq N) の初期ポイント残高は S_i です。

これから M 件のポイント調整処理を 1 番目から M 番目まで順番に 1 つずつ行います。 j 番目 (1 \leq j \leq M) の処理では、会員 T_j のその時点でのポイント残高に V_j を加算し、その結果と 0 の大きい方を新しいポイント残高とします。すなわち、処理前の会員 T_j のポイント残高が P であるとき、処理後のポイント残高は \max(P + V_j,\ 0) となります。各処理は次の処理が行われる前に完了します。なお、同一の会員に対して複数回の処理が行われることもあります。

ポイント残高に上限はありません。一方、上記のルールにより、各処理の後のポイント残高は常に 0 以上です。

すべてのポイント調整処理を順番に実行した後の、各会員のポイント残高を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq M)
  • -10^9 \leq V_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である
  • 出力すべき値はすべて 2^{63}-1 以下であることが保証される（符号付き 64 bit 整数の範囲に収まる）

入力

N M
S_1 S_2 \cdots S_N
T_1 V_1
T_2 V_2
\vdots
T_M V_M
  • 1 行目には、会員の人数を表す整数 N と、ポイント調整処理の件数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各会員の初期ポイント残高を表す整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • S_i は会員 i の初期ポイント残高を表す。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、 j 番目の処理で対象となる会員の番号を表す整数 T_j と、加算するポイント数を表す整数 V_j が、スペース区切りで与えられる。

出力

すべてのポイント調整処理を実行した後の、各会員のポイント残高を会員 1, 会員 2, \ldots, 会員 N の順にスペース区切りで 1 行に出力せよ。末尾に改行を出力すること。

入力例 1

3 4
100 200 300
1 50
2 -150
3 -400
1 -200

出力例 1

0 50 0

入力例 2

5 6
0 500 1000 750 300
3 -500
1 100
2 -600
4 250
5 -300
2 200

出力例 2

100 200 500 1000 0

入力例 3

10 12
1000000000 0 500000000 999999999 123456789 0 777777777 100000000 999999999 1
1 -1000000000
2 1000000000
3 -500000001
4 1
5 -123456790
6 0
7 -777777777
8 900000000
9 -1000000000
10 999999999
10 -500000000
3 1000000000

出力例 3

0 1000000000 1000000000 1000000000 0 0 0 1000000000 0 500000000

Score : 266 pts

Problem Statement

Takahashi manages the point card system of a shopping mall. The mall has N members, and member i (1 \leq i \leq N) has an initial point balance of S_i.

From now on, M point adjustment operations will be performed one by one in order from the 1-st to the M-th. In the j-th operation (1 \leq j \leq M), the value V_j is added to the current point balance of member T_j, and the new point balance is set to the maximum of the result and 0. That is, if member T_j's point balance before the operation is P, then the point balance after the operation becomes \max(P + V_j,\ 0). Each operation is completed before the next operation begins. Note that the same member may be subject to multiple operations.

There is no upper limit on the point balance. On the other hand, by the rule above, the point balance after each operation is always 0 or greater.

Determine the point balance of each member after all point adjustment operations have been performed in order.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq M)
  • -10^9 \leq V_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.
  • It is guaranteed that all values to be output are at most 2^{63}-1 (they fit within a signed 64-bit integer).

Input

N M
S_1 S_2 \cdots S_N
T_1 V_1
T_2 V_2
\vdots
T_M V_M
  • The first line contains an integer N representing the number of members and an integer M representing the number of point adjustment operations, separated by a space.
  • The second line contains integers S_1, S_2, \ldots, S_N representing the initial point balances of each member, separated by spaces.
  • S_i represents the initial point balance of member i.
  • In the following M lines, the j-th line (1 \leq j \leq M) contains an integer T_j representing the member number targeted by the j-th operation and an integer V_j representing the number of points to add, separated by a space.

Output

Print the point balance of each member after all point adjustment operations have been performed, in the order of member 1, member 2, \ldots, member N, separated by spaces, on a single line. Output a newline at the end.

Sample Input 1

3 4
100 200 300
1 50
2 -150
3 -400
1 -200

Sample Output 1

0 50 0

Sample Input 2

5 6
0 500 1000 750 300
3 -500
1 100
2 -600
4 250
5 -300
2 200

Sample Output 2

100 200 500 1000 0

Sample Input 3

10 12
1000000000 0 500000000 999999999 123456789 0 777777777 100000000 999999999 1
1 -1000000000
2 1000000000
3 -500000001
4 1
5 -123456790
6 0
7 -777777777
8 900000000
9 -1000000000
10 999999999
10 -500000000
3 1000000000

Sample Output 3

0 1000000000 1000000000 1000000000 0 0 0 1000000000 0 500000000