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

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

配点 : 266 点

問題文

高橋君は市内にある N 館の図書館を管理しています。図書館 i（1 \leq i \leq N）には M_i 個のジャンルがあり、各ジャンルには 1 から M_i までの番号が付けられています。

図書館 i のジャンル j（1 \leq j \leq M_i）の初期蔵書数は S_{i,j} 冊です。初期蔵書数が 0 冊のジャンルもありえます。

ある日、青木君が貸出記録を整理したところ、まだ処理されていない Q 件の貸出申請が順番に記録されていることが分かりました。高橋君はこれらの申請を 1 番目から Q 番目まで順に処理します。なお、初期蔵書数はこれらの貸出申請を処理する前の時点での蔵書数を表します。

k 番目（1 \leq k \leq Q）の貸出申請は「図書館 v_k のジャンル d_k の本を 1 冊借りる」という内容です。各貸出申請の処理は次のように行います。

  • 図書館 v_k のジャンル d_k の現在の蔵書数が 1 冊以上であれば、貸出は成功し、そのジャンルの蔵書数が 1 減ります。
  • 図書館 v_k のジャンル d_k の現在の蔵書数が 0 冊であれば、貸出は失敗し、蔵書数は変化しません。

すべての貸出申請を 1 番目から Q 番目まで順に処理した後、各図書館の各ジャンルの残り蔵書数と、貸出が失敗した申請の件数を出力してください。

制約

  • 1 \leq N \leq 1000
  • 1 \leq M_i \leq 1000
  • \sum_{i=1}^{N} M_i \leq 10^5
  • 0 \leq S_{i,j} \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq v_k \leq N
  • 1 \leq d_k \leq M_{v_k}
  • 入力はすべて整数である。

入力

N
M_1 S_{1,1} S_{1,2} \ldots S_{1,M_1}
M_2 S_{2,1} S_{2,2} \ldots S_{2,M_2}
\vdots
M_N S_{N,1} S_{N,2} \ldots S_{N,M_N}
Q
v_1 d_1
v_2 d_2
\vdots
v_Q d_Q
  • 1 行目には、図書館の数を表す整数 N が与えられる。
  • 続く N 行のうち i 番目の行（1 \leq i \leq N）には、図書館 i のジャンル数 M_i と、各ジャンルの初期蔵書数 S_{i,1}, S_{i,2}, \ldots, S_{i,M_i} が、この順にスペース区切りで与えられる。
  • その次の行には、貸出申請の件数を表す整数 Q が与えられる。
  • 続く Q 行のうち k 番目の行（1 \leq k \leq Q）には、k 番目の貸出申請の対象となる図書館の番号 v_k とジャンルの番号 d_k がスペース区切りで与えられる。

出力

N + 1 行で出力してください。

  • i 行目（1 \leq i \leq N）には、すべての貸出申請を処理した後の図書館 i の各ジャンルの残り蔵書数を、ジャンル 1 からジャンル M_i の順に M_i 個の整数としてスペース区切りで出力してください。
  • N + 1 行目には、貸出が失敗した申請の件数を 1 つの整数として出力してください。

入力例 1

2
2 3 1
1 0
4
1 1
1 2
1 2
2 1

出力例 1

2 0
0
2

入力例 2

3
3 5 0 2
2 1 1
2 3 0
8
1 2
1 1
2 1
2 2
3 2
1 3
1 3
3 1

出力例 2

4 0 0
0 0
2 0
2

入力例 3

4
3 1000000000 0 5
4 2 3 1 0
1 100
2 10 20
12
1 1
1 2
1 2
1 3
2 4
2 4
3 1
3 1
4 1
4 2
4 2
2 3

出力例 3

999999999 0 4
2 3 0 0
98
9 18
4

Score : 266 pts

Problem Statement

Takahashi manages N libraries in the city. Library i (1 \leq i \leq N) has M_i genres, and each genre is numbered from 1 to M_i.

The initial number of books in genre j (1 \leq j \leq M_i) of library i is S_{i,j}. It is possible for a genre to have an initial book count of 0.

One day, Aoki organized the lending records and found that there are Q unprocessed lending requests recorded in order. Takahashi will process these requests sequentially from the 1-st to the Q-th. The initial book counts represent the number of books at the time before processing these lending requests.

The k-th lending request (1 \leq k \leq Q) is "borrow 1 book of genre d_k from library v_k." Each lending request is processed as follows:

  • If the current number of books of genre d_k in library v_k is 1 or more, the lending succeeds, and the number of books of that genre decreases by 1.
  • If the current number of books of genre d_k in library v_k is 0, the lending fails, and the number of books does not change.

After processing all lending requests from the 1-st to the Q-th in order, output the remaining number of books for each genre in each library, and the number of requests that failed.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq M_i \leq 1000
  • \sum_{i=1}^{N} M_i \leq 10^5
  • 0 \leq S_{i,j} \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq v_k \leq N
  • 1 \leq d_k \leq M_{v_k}
  • All input values are integers.

Input

N
M_1 S_{1,1} S_{1,2} \ldots S_{1,M_1}
M_2 S_{2,1} S_{2,2} \ldots S_{2,M_2}
\vdots
M_N S_{N,1} S_{N,2} \ldots S_{N,M_N}
Q
v_1 d_1
v_2 d_2
\vdots
v_Q d_Q
  • The first line contains an integer N representing the number of libraries.
  • Among the following N lines, the i-th line (1 \leq i \leq N) contains the number of genres M_i in library i and the initial book counts S_{i,1}, S_{i,2}, \ldots, S_{i,M_i} for each genre, given in this order separated by spaces.
  • The next line contains an integer Q representing the number of lending requests.
  • Among the following Q lines, the k-th line (1 \leq k \leq Q) contains the library number v_k and the genre number d_k for the k-th lending request, separated by a space.

Output

Output N + 1 lines.

  • On the i-th line (1 \leq i \leq N), output the remaining number of books for each genre of library i after processing all lending requests, as M_i integers in order from genre 1 to genre M_i, separated by spaces.
  • On the (N + 1)-th line, output the number of failed lending requests as a single integer.

Sample Input 1

2
2 3 1
1 0
4
1 1
1 2
1 2
2 1

Sample Output 1

2 0
0
2

Sample Input 2

3
3 5 0 2
2 1 1
2 3 0
8
1 2
1 1
2 1
2 2
3 2
1 3
1 3
3 1

Sample Output 2

4 0 0
0 0
2 0
2

Sample Input 3

4
3 1000000000 0 5
4 2 3 1 0
1 100
2 10 20
12
1 1
1 2
1 2
1 3
2 4
2 4
3 1
3 1
4 1
4 2
4 2
2 3

Sample Output 3

999999999 0 4
2 3 0 0
98
9 18
4