A - 図書館の貸出管理 解説 /

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

配点 : 266 点

問題文

高橋君は学校の図書館で司書のアルバイトをしています。

図書館には N 種類の本があり、それぞれの本には 1 から N までの管理番号が付けられています。管理番号 i の本の現在の蔵書数は A_i 冊です。

今日、 M 件の貸出申請が届きました。 j 番目の貸出申請では、管理番号 B_j の本を C_j 冊貸し出すよう求められています。

高橋君は各貸出申請を j = 1, 2, \ldots, M の順に処理します。各貸出申請を処理する際、対象の本の現在の蔵書数が申請された冊数以上であれば、蔵書数から申請された冊数を差し引きます。蔵書数が申請された冊数未満の場合は、その貸出申請はスキップされ、蔵書数は変化しません。

すべての貸出申請を処理した後、各本の最終的な蔵書数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq N (1 \leq j \leq M)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M
A_1 A_2 \ldots A_N
B_1 C_1
B_2 C_2
\vdots
B_M C_M
  • 1 行目には、本の種類数を表す N と、貸出申請の件数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各本の初期蔵書数を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く M 行にわたって、貸出申請の情報が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、 j 番目の貸出申請で対象となる管理番号 B_j と、貸し出す冊数 C_j が、スペース区切りで与えられる。

出力

すべての貸出申請を処理した後の、各本の最終的な蔵書数を、管理番号 1 から管理番号 N の順にスペース区切りで 1 行で出力してください。

入力例 1

3 4
5 3 2
1 2
2 1
1 4
3 3

出力例 1

3 2 2

入力例 2

5 6
10 5 8 3 7
3 4
1 10
2 5
3 5
4 3
4 1

出力例 2

0 0 4 0 7

入力例 3

8 10
1000000000 500 100 250 999999999 1 50 300
1 999999999
1 1
5 1000000000
6 1
6 1
3 50
3 50
3 1
7 25
8 301

出力例 3

0 500 0 250 999999999 0 25 300

Score : 266 pts

Problem Statement

Takahashi is working a part-time job as a librarian at his school's library.

The library has N types of books, each assigned a catalog number from 1 to N. The current stock of the book with catalog number i is A_i copies.

Today, M lending requests have been received. The j-th lending request asks to lend out C_j copies of the book with catalog number B_j.

Takahashi processes each lending request in the order j = 1, 2, \ldots, M. When processing each lending request, if the current stock of the requested book is greater than or equal to the requested number of copies, the requested number of copies is subtracted from the stock. If the stock is less than the requested number of copies, the lending request is skipped and the stock remains unchanged.

After processing all lending requests, determine the final stock of each book.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq N (1 \leq j \leq M)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers

Input

N M
A_1 A_2 \ldots A_N
B_1 C_1
B_2 C_2
\vdots
B_M C_M
  • The first line contains N, the number of types of books, and M, the number of lending requests, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N, the initial stock of each book, separated by spaces.
  • The following M lines contain the lending request information.
  • The (2 + j)-th line (1 \leq j \leq M) contains the catalog number B_j and the number of copies C_j for the j-th lending request, separated by a space.

Output

After processing all lending requests, output the final stock of each book in a single line, in order from catalog number 1 to catalog number N, separated by spaces.

Sample Input 1

3 4
5 3 2
1 2
2 1
1 4
3 3

Sample Output 1

3 2 2

Sample Input 2

5 6
10 5 8 3 7
3 4
1 10
2 5
3 5
4 3
4 1

Sample Output 2

0 0 4 0 7

Sample Input 3

8 10
1000000000 500 100 250 999999999 1 50 300
1 999999999
1 1
5 1000000000
6 1
6 1
3 50
3 50
3 1
7 25
8 301

Sample Output 3

0 500 0 250 999999999 0 25 300