E - 図書館の蔵書点検 解説 /

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

配点 : 466 点

問題文

高橋君は大きな図書館の司書をしています。この図書館には N 個の書棚が一列に並んでおり、左から順に番号 1, 2, \ldots, N が付けられています。

書棚 i（1 \leq i \leq N）には A_i 冊の本が収められています。これらの本は現在修復作業中であり、書棚 i の本はすべて第 D_i 日目に修復が完了します。修復が完了した本は貸し出し可能となります。すなわち、書棚 i の本は第 D_i 日目以降（第 D_i 日目を含む）に貸し出すことができます。書棚 i の本が貸し出される際、利用者は本 1 冊につき V_i 円の利用料を図書館に納めます。

高橋君は Q 個の貸し出し計画を検討しています。各計画は互いに独立であり、ある計画で本が貸し出されても、他の計画には影響しません。

計画 j（1 \leq j \leq Q）では、連続する書棚の区間 [L_j, R_j]（1 \leq L_j \leq R_j \leq N）と日付 T_j が決まっています。この計画では、区間 [L_j, R_j] に含まれる書棚のうち、第 T_j 日目の時点で修復が完了しているもの（すなわち D_i \leq T_j を満たす書棚 i）について、その書棚の A_i 冊すべてが貸し出されます。修復が完了していない書棚の本は貸し出されません。

書棚 i の A_i 冊すべてが貸し出された場合、得られる利用料は A_i \times V_i 円です。

それぞれの計画について、貸し出しによって得られる利用料の合計額を求めてください。すなわち、計画 j で得られる利用料の合計額は、

\sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i

です。

制約

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^4
  • 1 \leq D_i \leq 10^5
  • 1 \leq V_i \leq 10^4
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq T_j \leq 10^5
  • 入力はすべて整数である
  • 各計画について、答えは 2 \times 10^{13} 以下である

入力

N Q
A_1 D_1 V_1
A_2 D_2 V_2
\vdots
A_N D_N V_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • 1 行目には、書棚の数 N と貸し出し計画の数 Q がスペース区切りで与えられる。
  • 続く N 行のうち i 行目には、書棚 i の本の冊数 A_i、修復完了日 D_i、本 1 冊あたりの利用料 V_i がスペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、計画 j の区間の左端 L_j、右端 R_j、日付 T_j がスペース区切りで与えられる。

出力

Q 行出力してください。j 行目には、計画 j で得られる利用料の合計額を整数で出力してください。

入力例 1

5 4
2 1 100
3 3 50
1 2 200
5 5 10
4 3 25
1 3 2
2 5 3
1 5 5
4 4 4

出力例 1

400
450
700
0

入力例 2

3 5
1 10 5
2 20 7
3 30 11
1 3 9
1 1 10
2 3 25
3 3 30
1 3 100

出力例 2

0
5
14
33
52

入力例 3

10 8
5 4 120
2 1 300
7 6 80
1 3 1000
4 5 250
6 2 90
3 8 400
8 7 60
10 4 30
9 9 110
1 10 4
3 7 5
2 9 2
5 10 8
1 1 3
4 6 10
7 10 6
2 5 1

出力例 3

3040
2540
1140
3520
0
2540
300
600

入力例 4

30 20
10 15 100
25 3 40
7 22 500
100 1 20
13 18 70
6 9 1000
80 30 15
2 5 600
45 12 90
11 7 250
9 40 800
30 25 35
16 2 120
5 17 900
60 11 45
3 35 700
22 6 110
14 28 330
50 19 55
8 4 1000
19 23 75
4 14 650
70 8 25
12 31 400
33 10 60
1 100000 10000
90 13 30
18 21 200
27 16 85
40 24 95
1 30 10
1 30 100000
5 20 18
10 15 7
16 30 25
1 8 5
21 26 99999
26 26 100000
3 27 12
8 23 30
12 29 20
2 2 2
4 4 1
14 18 35
19 30 23
6 17 11
24 30 31
1 1 14
7 13 40
28 30 15

出力例 4

29020
95820
34450
4670
33320
4200
12555
10000
34770
41735
33615
0
2000
16340
27100
16990
19175
0
19370
0

入力例 5

1 1
10000 100000 10000
1 1 99999

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi works as a librarian at a large library. This library has N bookshelves arranged in a row, numbered 1, 2, \ldots, N from left to right.

Bookshelf i (1 \leq i \leq N) contains A_i books. These books are currently under restoration, and all books on bookshelf i will have their restoration completed on day D_i. Once restoration is complete, the books become available for lending. That is, books on bookshelf i can be lent out from day D_i onward (including day D_i). When books from bookshelf i are lent out, the user pays a fee of V_i yen per book to the library.

Takahashi is considering Q lending plans. Each plan is independent of the others; books being lent out in one plan do not affect other plans.

In plan j (1 \leq j \leq Q), a contiguous interval of bookshelves [L_j, R_j] (1 \leq L_j \leq R_j \leq N) and a date T_j are specified. In this plan, among the bookshelves in the interval [L_j, R_j], those whose restoration is complete by day T_j (i.e., bookshelves i satisfying D_i \leq T_j) will have all A_i books lent out. Books on bookshelves whose restoration is not yet complete will not be lent out.

When all A_i books on bookshelf i are lent out, the fee earned is A_i \times V_i yen.

For each plan, determine the total fee earned from the lending. That is, the total fee earned in plan j is:

\sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i

Constraints

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^4
  • 1 \leq D_i \leq 10^5
  • 1 \leq V_i \leq 10^4
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq T_j \leq 10^5
  • All inputs are integers
  • For each plan, the answer is at most 2 \times 10^{13}

Input

N Q
A_1 D_1 V_1
A_2 D_2 V_2
\vdots
A_N D_N V_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • The first line contains the number of bookshelves N and the number of lending plans Q, separated by a space.
  • In the following N lines, the i-th line contains the number of books A_i on bookshelf i, the restoration completion day D_i, and the fee per book V_i, separated by spaces.
  • In the following Q lines, the j-th line contains the left endpoint L_j, right endpoint R_j, and date T_j for plan j, separated by spaces.

Output

Output Q lines. On the j-th line, output the total fee earned in plan j as an integer.

Sample Input 1

5 4
2 1 100
3 3 50
1 2 200
5 5 10
4 3 25
1 3 2
2 5 3
1 5 5
4 4 4

Sample Output 1

400
450
700
0

Sample Input 2

3 5
1 10 5
2 20 7
3 30 11
1 3 9
1 1 10
2 3 25
3 3 30
1 3 100

Sample Output 2

0
5
14
33
52

Sample Input 3

10 8
5 4 120
2 1 300
7 6 80
1 3 1000
4 5 250
6 2 90
3 8 400
8 7 60
10 4 30
9 9 110
1 10 4
3 7 5
2 9 2
5 10 8
1 1 3
4 6 10
7 10 6
2 5 1

Sample Output 3

3040
2540
1140
3520
0
2540
300
600

Sample Input 4

30 20
10 15 100
25 3 40
7 22 500
100 1 20
13 18 70
6 9 1000
80 30 15
2 5 600
45 12 90
11 7 250
9 40 800
30 25 35
16 2 120
5 17 900
60 11 45
3 35 700
22 6 110
14 28 330
50 19 55
8 4 1000
19 23 75
4 14 650
70 8 25
12 31 400
33 10 60
1 100000 10000
90 13 30
18 21 200
27 16 85
40 24 95
1 30 10
1 30 100000
5 20 18
10 15 7
16 30 25
1 8 5
21 26 99999
26 26 100000
3 27 12
8 23 30
12 29 20
2 2 2
4 4 1
14 18 35
19 30 23
6 17 11
24 30 31
1 1 14
7 13 40
28 30 15

Sample Output 4

29020
95820
34450
4670
33320
4200
12555
10000
34770
41735
33615
0
2000
16340
27100
16990
19175
0
19370
0

Sample Input 5

1 1
10000 100000 10000
1 1 99999

Sample Output 5

0