Telka

Recently there was a population census in Mirko's country. Along with numerous other data that was
being collected, very important part was the data about television ratings.
Each of the N citizens provided two timestamps in the following format:
HH:MM:SS – HH:MM:SS
The first timestamp describes the time of the day when citizen started watching television, and the
second one the time when that citizen stopped watching. Citizen also watched television during the first
and the last second of the given interval. Note that it is possible to start watching before midnight, eg.,
at 23:45:30, and not finish until the next day, eg., at 01:15:00.
After all the data has been collected, statisticians are gathered in order to analyse it.
We define the popularity of some second as the total number of citizens that were watching
television during that second. Furthermore, the popularity of the given time interval is defined as the
sum of popularities of seconds contained within that interval, divided by the length of the interval.
Calculate the popularities of the Q given time intervals that are of special interest to the statisticians.

In test cases worth a total of 25% points, \(N \le 500\) and \(Q \le 500\) will hold.
In test cases worth a total of 25% points, \(N \le 500\) and \(Q \le 100\,000\) will hold.
In test cases worth a total of 25% points, \(N \le 100\,000\) and \(Q \le 500\) will hold.
EXAMPLE TEST DATA
input
5
00:00:\(00 - 00\):00:01
00:00:\(01 - 00\):00:03
00:00:\(00 - 00\):00:02
00:00:\(05 - 00\):00:09
00:00:\(06 - 00\):00:06
5
00:00:\(00 - 00\):00:03
00:00:\(07 - 00\):00:09
00:00:\(06 - 00\):00:06
00:00:\(05 - 00\):00:09
00:00:\(00 - 00\):00:09
output
2.0000000000
1.0000000000
2.0000000000
1.2000000000
1.4000000000
input
3
00:00:\(00 - 10\):00:00
10:00:\(00 - 00\):00:00
01:01:\(01 - 02\):02:02
4
00:00:\(00 - 23\):59:59
23:59:\(59 - 23\):59:58
23:59:\(59 - 23\):59:59
08:34:\(43 - 12\):22:17
output
1.0424074074
1.0424074074
1.0000000000
1.0000732332

The first line of input contains integer N (\(N \le 100\,000\)), the number of citizens.
The following N lines each contain two timestamps given by that citizen, in the format described above
(\(0 \le HH \le 23\), \(0 \le MM \le 59\), \(0 \le SS \le 59\)).
In the following line there is an integer Q (\(Q \le 100\,000\)), describing the number of time intervals that
statisticians are interested in.
The following Q lines contain time intervals in the same format as above.

For each of the Q given intervals, output it's popularity in seperate line.
Solution will be accepted if apsolute or relative error is at most \(10^{-6}\).

생성자가 기록되지 않았습니다.

출처 COI 2011