Recently there was a population census in Mirko's country. Along with numerous other data that were being collected, a 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 a citizen started watching television, and the second one the time when that citizen stopped watching. The 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, e.g., at 23:45:30, and not finish until the next day, e.g., 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.

Input Specification

The first line of input contains integer $N$ $(N\le 100000)$, the number of citizens.

The following $N$ lines each contain two timestamps given by that citizen, in the format described above $(0\le \text{HH}\le 23,0\le \text{MM}\le 59,0\le \text{SS}\le 59)$.

In the following line there is an integer $Q$ $(Q\le 100000)$, describing the number of time intervals that statisticians are interested in.

The following $Q$ lines contain time intervals in the same format as above.

Output Specification

For each of the $Q$ given intervals, output its popularity on a separate line.

A solution will be accepted if the absolute or relative error is at most ${10}^{-6}$.

Scoring

In test cases worth a total of $25\mathrm{\%}$ points, $N\le 500$ and $Q\le 500$ will hold.

In test cases worth a total of $25\mathrm{\%}$ points, $N\le 500$ and $Q\le 100000$ will hold.

In test cases worth a total of $25\mathrm{\%}$ points, $N\le 100000$ and $Q\le 500$ will hold.

Sample Input 1

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

Sample Output 1

2.0000000000
1.0000000000
2.0000000000
1.2000000000
1.4000000000

Sample Input 2

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

Sample Output 2

1.0424074074
1.0424074074
1.0000000000
1.0000732332