Under construction

Still being built. Things may change

Water Main Break

Interview

Time limit1sMemory limit128 MB

Summary
Given several water main breaks with start, end, and flow rate, sum the gallons leaked during each second of a given query interval.
Level

Easy3 of 10

Topics
Array, Simulation, Implementation
Solved
No attempts yet

Problem

A water main can break and leak water for a while before it is repaired. In this problem you are given information about several water main breaks — when each one started, when each one ended, and the rate at which water flowed out — together with a time interval. Your task is to compute the total amount of water wasted during that interval.

Time is measured in whole seconds. A water main break that starts at second si and ends at second fi leaks ri gallons at each of the seconds si, si+1, ..., fi (both endpoints included); it is considered repaired from second fi + 1 onward.

Input

The first line contains the number K of data sets. Each data set has the following form:

  • The first line contains a single integer n (0 ≤ n ≤ 30), the number of water main breaks.
  • The second line contains two integers s and f (0 ≤ s ≤ f ≤ 1000), the start and finish seconds of the interval [s, f] over which the wasted water must be counted.
  • Each of the next n lines describes one water main break with three integers si, fi, ri (0 ≤ si ≤ fi ≤ 1000, 0 ≤ ri ≤ 1000): its start second, its finish second, and its flow rate in gallons per second.

Output

For each data set, first print a line Data Set x:, where x is the data set's number starting from 1. On the next line print the total number of gallons of water wasted during the interval [s, f]; this counts water leaking at each of the seconds s, s+1, ..., f. Separate the output of consecutive data sets with a single blank line.

Examples7

  1. Example 1

    Input
    2
1
3 5
2 4 1
5
4 9
4 4 1000
1 7 10
10 15 1000
3 11 100
7 8 1
    Expected output
    Data Set 1:
2

Data Set 2:
1642

  2. Example 2

    Input
    1
1
0 10
0 10 5
    Expected output
    Data Set 1:
55

  3. Example 3

    Input
    1
0
0 1000
    Expected output
    Data Set 1:
0

  4. Example 4

    Input
    1
1
50 60
0 40 100
    Expected output
    Data Set 1:
0

  5. Example 5

    Input
    1
1
0 10
0 10 0
    Expected output
    Data Set 1:
0

  6. Example 6

    Input
    1
2
5 5
0 10 3
5 5 7
    Expected output
    Data Set 1:
10

  7. Example 7

    Input
    1
2
10 20
20 30 5
0 10 7
    Expected output
    Data Set 1:
12