There is a Segway race in the city of Dubrovnik. The race track consists of three sections, each of
which is meters long – therefore, the total length of the track is
meters. Based on the
limitations of her/his Segway battery, each rider has a strategy: the speed at which he rides on the first
meters, the speed on the next
meters, and the speed on the last
meters, except when
allowed to speed up the Segway to the maximum speed (explained in the next paragraph).
Unfortunately, the Segways are very slow, taking between and
seconds for each meter. Therefore,
the speeds in this task are given in seconds per meter (instead of meters per second).
Along the track there are several acceleration points (accelerators). When a rider reaches an accelerator,
his Segway gets extra power to ride at the maximum speed of second per meter for the next
meters, where
is the number of riders strictly ahead of him at the moment he reached the
accelerator (including those who have already completed the race). The rider is unable to use another
accelerator before he has spent all extra power from the previous accelerator. At that moment, if there
are no new accelerators, the rider continues to move at his default speed for the corresponding track
section.
Assume that a rider will always use an available accelerator, even if it might not be the optimal strategy. An accelerator can be used by multiple riders, even at the same time. Your task is to write a program that simulates this race. Assuming that all Segway riders start at the same time, print the finish time for each rider in seconds.
Input Specification
The first line contains an integer
, the number of riders.
The of the following
lines contains three integers between
and
: the default speed of the
rider on the first
meters, the next
meters, and the last
meters of the track.
The next line contains an integer
, the number of acceleration points.
If
, the following line contains a strictly increasing sequence of
integers between
and
: the
distances of the accelerators from the beginning of the track in meters.
Output Specification
You should print lines, where the
line contains the required time for the
rider.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 15 | |
2 | 40 | |
3 | 45 | No additional constraints. |
Sample Input 1
2
1 2 3
4 5 6
0
Sample Output 1
600
1500
Explanation of Sample Output 1
There are no accelerators and both riders use their default speeds.
Sample Input 2
3
5 5 5
6 2 10
10 9 2
2
100 199
Sample Output 2
1496
1799
2075
Explanation of Sample Output 2
Rider #1 does not use the first accelerator (there is nobody ahead of
him), but uses the second accelerator because rider #2 overtakes him in the meantime. Overall, rider
#1 rides meters for
seconds each, and
meter for
second.
Rider #2 uses the first accelerator (there is one rider ahead), but does not use the second one. Overall,
he rides
meters for
seconds each,
meter for
second,
meters for
seconds each, and
meters for
seconds each.
Rider #3 after each accelerator rides
meters at maximum speed. Overall, he rides
meters for
seconds each,
meters for
second each,
meters for
seconds each,
meters for
second each,
and
meters for
seconds each.
Sample Input 3
5
2 2 2
6 6 6
8 8 8
9 9 9
10 10 10
2
297 298
Sample Output 3
600
1790
2386
2676
2973
Explanation of Sample Output 3
Of the two accelerators near the end of the track, rider #1 does not use
any. Rider #2 uses both (for meter) and then rides for another
meter at her default speed. Rider #3
uses the first accelerator (for
meters) and then rides for another
meter at her default speed. Riders
#4 and #5 use extra power from the first accelerator all the way to the end of the track.
Comments