인기도 조사
시간 제한1초메모리 제한128 MB
하루 안에서 자정을 넘길 수 있는 N개의 시청 구간이 주어질 때, 초 단위 차분 배열과 누적합으로 Q개의 질의 구간에 대한 평균 시청자 수를 구하는 문제입니다.
문제
최근 한 나라에서 인구 조사가 실시되었다. 실제 목적은 각 초마다 텔레비전을 보고 있던 사람 수를 바탕으로 시청 인기도를 구하는 것이다.
각 사람이 텔레비전을 본 시간 구간은 다음 형식으로 주어진다.
HH:MM:SS - HH:MM:SS
앞의 시간은 시청을 시작한 시각이고, 뒤의 시간은 시청을 끝낸 시각이다. 시작 시각과 종료 시각에 해당하는 초도 모두 시청한 것으로 본다. 종료 시각이 시작 시각보다 이르면, 그 사람은 자정을 지나 다음 날 종료 시각까지 시청한 것이다.
어떤 초의 인기도는 그 초에 텔레비전을 보고 있는 사람 수이다. 한 구간의 인기도는 그 구간에 포함된 모든 초의 인기도 합을 구간 길이(초 단위)로 나눈 값이다.
Q개의 조사 구간이 주어질 때, 각 구간의 평균 인기도를 구하라.
입력
첫째 줄에 사람 수 N이 주어진다. (N ≤ 100,000)
다음 N개 줄에는 각 사람이 텔레비전을 시청한 구간이 HH:MM:SS - HH:MM:SS 형식으로 주어진다. 각 시각은 0 ≤ HH ≤ 23, 0 ≤ MM ≤ 59, 0 ≤ SS ≤ 59를 만족한다.
다음 줄에 조사 구간 수 Q가 주어진다. (Q ≤ 100,000)
다음 Q개 줄에는 인기도를 구할 구간이 같은 형식으로 주어진다.
출력
Q개의 줄에 각 조사 구간의 인기도를 하나씩 출력한다. 정답과의 오차는 10^-6 이하까지 허용된다.