A1437.[COCI-2010_2011-olympiad]#5 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:0
0.
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.

The first line of input contains integer N (N ≤ 100 000), the number of citizens.
The following N lines each contain two timestamps given by that citizen, in the format described above (0 ≤ HH ≤ 23, 0 ≤ MM ≤ 59, 0 ≤ SS ≤ 59).
In the following line there is an integer Q (Q ≤ 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.

In test cases worth a total of 25% points, N ≤ 500 and Q ≤ 500 will hold.
In test cases worth a total of 25% points, N ≤ 500 and Q ≤ 100 000 will hold.
In test cases worth a total of 25% points, N ≤ 100 000 and Q ≤ 500 will hold.