A - 旅行の立て替え精算 解説 /

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

配点 : 266 点

問題文

N 人のグループが旅行に行きました。メンバーには 1 から N までの番号が付けられています。旅行中に発生した費用は、そのつどメンバーの誰か一人が立て替えて支払いました。旅行が終わった後、全員で費用を公平に精算することにしました。

旅行中には合計 M 回の支払いが発生しました。i 回目 (1 \leq i \leq M) の支払いでは、人 P_i が C_i 円を立て替えて支払いました。この支払いは K_i 人のメンバーが利用したもので、利用者は B_{i,1}, B_{i,2}, \ldots, B_{i,K_i} です。立て替えた人 P_i 自身が利用者に含まれることも、含まれないこともあります。各支払いについて、利用した K_i 人で均等に費用を負担するものとします。すなわち、利用者一人あたりの負担額は \frac{C_i}{K_i} 円です。

すべての支払いを考慮したうえで、人 j (1 \leq j \leq N) について、精算額 D_j を次のように定義します。

D_j = \sum_{\substack{1 \leq i \leq M \\ P_i = j}} C_i \;-\; \sum_{\substack{1 \leq i \leq M \\ j \in \{B_{i,1}, \ldots, B_{i,K_i}\}}} \frac{C_i}{K_i}

すなわち、D_j は「人 j が実際に立て替えた合計金額」から「人 j が本来負担すべき合計金額」を引いた値です。人 j がどの支払いでも立て替えを行っていない場合、立て替えた合計金額は 0 円とします。同様に、人 j がどの支払いの利用者にも含まれていない場合、負担すべき合計金額は 0 円とします。

D_j が正なら人 j は D_j 円を受け取るべきであり、D_j が負なら人 j は |D_j| 円を支払うべきであり、D_j = 0 なら精算の必要はありません。

N 人全員について D_j の値をそれぞれ求めてください。なお、すべての \frac{C_i}{K_i} は整数になることが保証されるため、D_j も必ず整数になります。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq P_i \leq N
  • 1 \leq C_i \leq 10^9
  • 1 \leq K_i \leq N
  • 1 \leq B_{i,1} < B_{i,2} < \ldots < B_{i,K_i} \leq N
  • P_i は B_{i,1}, B_{i,2}, \ldots, B_{i,K_i} に含まれるとは限らない
  • \frac{C_i}{K_i} は整数である
  • \sum_{i=1}^{M} K_i \leq 10^5
  • 入力はすべて整数である

入力

N M
P_1 C_1 K_1 B_{1,1} B_{1,2} \ldots B_{1,K_1}
P_2 C_2 K_2 B_{2,1} B_{2,2} \ldots B_{2,K_2}
\vdots
P_M C_M K_M B_{M,1} B_{M,2} \ldots B_{M,K_M}
  • 1 行目には、グループの人数 N と支払い回数 M が、スペース区切りで与えられる。
  • 続く M 行にわたって、各支払いの情報が与えられる。
  • そのうち i 番目の行 (1 \leq i \leq M) では、i 回目の支払いについて、立て替えた人の番号 P_i、金額 C_i、利用者数 K_i、利用者の番号 B_{i,1}, B_{i,2}, \ldots, B_{i,K_i} がスペース区切りで与えられる。

出力

N 行出力せよ。j 行目 (1 \leq j \leq N) には、人 j の精算額 D_j の値を整数として出力せよ。D_j が負の場合は負の符号を付けて出力し、D_j = 0 の場合は 0 を出力せよ。

入力例 1

3 2
1 6000 3 1 2 3
2 4000 2 2 3

出力例 1

4000
0
-4000

入力例 2

5 4
1 10000 5 1 2 3 4 5
3 6000 3 1 2 3
2 8000 2 2 4
5 3000 3 3 4 5

出力例 2

6000
0
1000
-7000
0

入力例 3

6 5
1 12000 6 1 2 3 4 5 6
2 9000 3 1 2 3
4 8000 4 1 4 5 6
6 5000 2 2 6
3 7000 2 3 5

出力例 3

5000
1500
-1500
4000
-7500
-1500

Score : 266 pts

Problem Statement

A group of N people went on a trip. The members are numbered from 1 to N. Expenses incurred during the trip were each paid upfront by one of the members on behalf of the others. After the trip, they decided to settle all expenses fairly among everyone.

A total of M payments were made during the trip. For the i-th payment (1 \leq i \leq M), person P_i paid C_i yen upfront. This payment was for K_i members who used it, and the users are B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}. The person P_i who paid upfront may or may not be included among the users. For each payment, the cost is to be shared equally among the K_i users. That is, the amount each user should bear is \frac{C_i}{K_i} yen.

Considering all payments, define the settlement amount D_j for person j (1 \leq j \leq N) as follows:

D_j = \sum_{\substack{1 \leq i \leq M \\ P_i = j}} C_i \;-\; \sum_{\substack{1 \leq i \leq M \\ j \in \{B_{i,1}, \ldots, B_{i,K_i}\}}} \frac{C_i}{K_i}

In other words, D_j is the value obtained by subtracting "the total amount person j should have borne" from "the total amount person j actually paid upfront." If person j did not pay upfront for any payment, the total amount paid upfront is 0 yen. Similarly, if person j is not included as a user in any payment, the total amount they should bear is 0 yen.

If D_j is positive, person j should receive D_j yen. If D_j is negative, person j should pay |D_j| yen. If D_j = 0, no settlement is needed.

Determine the value of D_j for all N people. Note that it is guaranteed that every \frac{C_i}{K_i} is an integer, so D_j is always an integer as well.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq P_i \leq N
  • 1 \leq C_i \leq 10^9
  • 1 \leq K_i \leq N
  • 1 \leq B_{i,1} < B_{i,2} < \ldots < B_{i,K_i} \leq N
  • P_i is not necessarily included among B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}
  • \frac{C_i}{K_i} is an integer
  • \sum_{i=1}^{M} K_i \leq 10^5
  • All input values are integers

Input

N M
P_1 C_1 K_1 B_{1,1} B_{1,2} \ldots B_{1,K_1}
P_2 C_2 K_2 B_{2,1} B_{2,2} \ldots B_{2,K_2}
\vdots
P_M C_M K_M B_{M,1} B_{M,2} \ldots B_{M,K_M}
  • The first line contains the number of people in the group N and the number of payments M, separated by a space.
  • The following M lines provide the information for each payment.
  • The i-th of these lines (1 \leq i \leq M) contains, for the i-th payment, the number of the person who paid upfront P_i, the amount C_i, the number of users K_i, and the user numbers B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}, separated by spaces.

Output

Output N lines. On the j-th line (1 \leq j \leq N), output the settlement amount D_j for person j as an integer. If D_j is negative, output it with a negative sign. If D_j = 0, output 0.

Sample Input 1

3 2
1 6000 3 1 2 3
2 4000 2 2 3

Sample Output 1

4000
0
-4000

Sample Input 2

5 4
1 10000 5 1 2 3 4 5
3 6000 3 1 2 3
2 8000 2 2 4
5 3000 3 3 4 5

Sample Output 2

6000
0
1000
-7000
0

Sample Input 3

6 5
1 12000 6 1 2 3 4 5 6
2 9000 3 1 2 3
4 8000 4 1 4 5 6
6 5000 2 2 6
3 7000 2 3 5

Sample Output 3

5000
1500
-1500
4000
-7500
-1500