D - Takahashi's Expectation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

高橋くんは、これから N 個のプレゼントをもらいます。

高橋くんにはテンションという非負整数のパラメータがあり、テンションはプレゼントをもらうごとに変動します。 それぞれのプレゼントは価値 P 、テンション上げ度 A 、テンション下げ度 B という 3 つのパラメータをもち、これらのパラメータによって高橋くんのテンションは次のように変動します。

  • もらったプレゼントの価値 P がテンションの値以上であるとき、高橋くんはプレゼントに喜び、テンションが A だけ増加する。
  • もらったプレゼントの価値 P がテンションの値より小さいとき、高橋くんはプレゼントにがっかりし、テンションが B だけ減少する。ただし、高橋くんのテンションの値が B より小さかった場合、高橋くんのテンションは 0 になる。

i 番目 (1\le i\le N) に受け取るプレゼントの価値は P _ i 、テンション上げ度は A _ i 、テンション下げ度は B _ i です。

Q 個の質問が与えられるので、その全てに答えてください。 i 番目 (1\le i\le Q) の質問では、非負整数 X _ i が与えられるので次の質問に答えてください。

高橋くんのテンションがはじめ X _ i だったときの、N 個のプレゼントをすべて受け取ったあとの高橋くんのテンションを求めよ。

制約

  • 1\le N\le10000
  • 1\le P _ i\le500\ (1\le i\le N)
  • 1\le A _ i\le500\ (1\le i\le N)
  • 1\le B _ i\le500\ (1\le i\le N)
  • 1\le Q\le5\times10 ^ 5
  • 0\le X _ i\le10 ^ 9\ (1\le i\le Q)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
P _ 1 A _ 1 B _ 1
P _ 2 A _ 2 B _ 2
\vdots
P _ N A _ N B _ N
Q
X _ 1
X _ 2
\vdots
X _ Q

出力

Q 行にわたって出力せよ。 i 行目には、i 番目の質問に対する答えを出力せよ。

入力例 1

4
3 1 4
1 5 9
2 6 5
3 5 8
11
0
1
2
3
4
5
6
7
8
9
10

出力例 1

6
0
0
0
5
6
0
0
0
0
0

高橋くんのテンションがはじめ 10 だったとき、高橋くんのテンションは以下のように変動します。

  • 1 つめのプレゼントの価値 3 は高橋くんのテンション 10 未満なので、テンション下げ度 4 だけ高橋くんのテンションが減少し、高橋くんのテンションが 6 になる。
  • 2 つめのプレゼントの価値 1 は高橋くんのテンション 6 未満で、高橋くんのテンション 6 はテンション下げ度 9 未満なので、高橋くんのテンションが 0 になる。
  • 3 つめのプレゼントの価値 2 は高橋くんのテンション 0 以上なので、テンション上げ度 6 だけ高橋くんのテンションが増加し、高橋くんのテンションが 6 になる。
  • 4 つめのプレゼントの価値 3 は高橋くんのテンション 6 未満で、高橋くんのテンション 6 はテンション下げ度 8 未満なので、高橋くんのテンションが 0 になる。

よって、最終的な高橋くんのテンションは 0 になります。

入力例 2

3
500 500 500
500 500 500
500 500 500
1
1000000000

出力例 2

999998500

高橋くんのテンションが高すぎるため、最高のプレゼントを貰っていても高橋くんのテンションは下がり続けます。

入力例 3

20
124 370 105
280 200 420
425 204 302
435 141 334
212 287 231
262 410 481
227 388 466
222 314 366
307 205 401
226 460 452
336 291 119
302 104 432
478 348 292
246 337 403
102 404 371
368 399 417
291 416 351
236 263 231
170 415 482
101 339 184
20
1162
1394
1695
2501
3008
3298
4053
4093
4330
5199
5302
5869
5875
6332
6567
7483
7562
7725
9723
9845

出力例 3

339
339
339
339
339
339
339
339
339
339
339
339
339
389
339
643
722
885
2883
3005

Score : 425 points

Problem Statement

Takahashi will receive N presents.

He has a parameter called mood, which is a non-negative integer, and his mood changes every time he receives a present. Each present has three parameters: value P, mood increase A, and mood decrease B, and his mood changes as follows based on these parameters:

  • When the value P of the received present is greater than or equal to his mood, he is happy with the present, and his mood increases by A.
  • When the value P of the received present is less than his mood, he is disappointed with the present, and his mood decreases by B. However, if his mood is originally less than B, it becomes 0.

The i-th (1\le i\le N) present he receives has value P _ i, mood increase A _ i, and mood decrease B _ i.

You are given Q questions, so answer all of them. In the i-th (1\le i\le Q) question, you are given a non-negative integer X _ i, so answer the following question:

Find Takahashi's mood after receiving all N presents when his mood is initially X _ i.

Constraints

  • 1\le N\le10000
  • 1\le P _ i\le500\ (1\le i\le N)
  • 1\le A _ i\le500\ (1\le i\le N)
  • 1\le B _ i\le500\ (1\le i\le N)
  • 1\le Q\le5\times10 ^ 5
  • 0\le X _ i\le10 ^ 9\ (1\le i\le Q)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P _ 1 A _ 1 B _ 1
P _ 2 A _ 2 B _ 2
\vdots
P _ N A _ N B _ N
Q
X _ 1
X _ 2
\vdots
X _ Q

Output

Output Q lines. The i-th line should contain the answer to the i-th question.

Sample Input 1

4
3 1 4
1 5 9
2 6 5
3 5 8
11
0
1
2
3
4
5
6
7
8
9
10

Sample Output 1

6
0
0
0
5
6
0
0
0
0
0

When Takahashi's initial mood is 10, his mood changes as follows:

  • The value 3 of the first present is less than his mood 10, so his mood decreases by the mood decrease 4, and his mood becomes 6.
  • The value 1 of the second present is less than his mood 6, and Takahashi's mood 6 is less than the mood decrease 9, so his mood becomes 0.
  • The value 2 of the third present is not less than his mood 0, so his mood increases by the mood increase 6, and his mood becomes 6.
  • The value 3 of the fourth present is less than his mood 6, and Takahashi's mood 6 is less than the mood decrease 8, so his mood becomes 0.

Therefore, his final mood is 0.

Sample Input 2

3
500 500 500
500 500 500
500 500 500
1
1000000000

Sample Output 2

999998500

Because Takahashi's mood is too high, his mood keeps decreasing even when he receives the best presents.

Sample Input 3

20
124 370 105
280 200 420
425 204 302
435 141 334
212 287 231
262 410 481
227 388 466
222 314 366
307 205 401
226 460 452
336 291 119
302 104 432
478 348 292
246 337 403
102 404 371
368 399 417
291 416 351
236 263 231
170 415 482
101 339 184
20
1162
1394
1695
2501
3008
3298
4053
4093
4330
5199
5302
5869
5875
6332
6567
7483
7562
7725
9723
9845

Sample Output 3

339
339
339
339
339
339
339
339
339
339
339
339
339
389
339
643
722
885
2883
3005