24336번 - 가희와 무궁화호 스페셜 저지

문제

아래 [표 1]은 경부선에서 무궁화호가 정차하는 역을 나타냅니다.

[표 1] 경부선에서 무궁화호가 정차하는 역들

[표 1]에서 역 이름과 각각의 역에 대응되는 역 번호가 있습니다. Seoul 역은 1번, Busan역은 43번입니다. 역 번호가 증가하는 방향은 하행이고, 역 번호가 감소하는 방향은 상행입니다. 예를 들어 1번 Seoul 역에서 31번 Dongdaegu 역으로 가는 경우, 역 번호가 증가하는 방향이므로 하행이고, 43번 Busan 역에서 15번 Daejeon 역으로 가는 방향은 역 번호가 감소하는 방향이므로 상행입니다.

[표 1]에서 거리란 Seoul역으로부터의 거리를 의미합니다. 예를 들어 22번 Hwanggan역은 1번 Seoul역으로부터 226.2km 떨어져 있습니다.

가희가 타고 있는 무궁화호가 k개의 역, S₁, S₂, ... , S_k 순서대로 정차한다고 해 보겠습니다. 즉, x번째로 정차하는 역은 S_x입니다. 이때, 무궁화호는 S₁ 역을 출발, S₂ 역 도착, S₂ 역 출발, ... , S_k 역 도착순으로 수행하게 됩니다.

무궁화호가 시각 hh:mm에 역에 도착하거나 출발하는 것을 이벤트라고 정의하겠습니다. 가희가 타고 있는 무궁화호의 x번째 이벤트는 아래와 같이 정의됩니다.

• x가 홀수일 때, 무궁화호가 S_⌊x/2⌋+1 번째 역을 출발
• x가 짝수일 때, 무궁화호가 S_⌊x/2⌋+1 번째 역에 도착
• ⌊x⌋는 내림을 의미합니다.

예를 들어, 가희가 탄 무궁화호가 아래 [표 2]와 같이 18개 역을 순서대로 정차한다고 하겠습니다.

[표 2] 가희가 탄 무궁화호가 Seoul 역에서 Busan 역까지 가는 동안 정차하는 역의 예

가희가 탄 무궁화호는 18개 역에 정차하고, 이 중 3번째로 정차하는 역은 Suwon역입니다. 또한, 3번째로 발생하는 이벤트는 Yeongdeungpo역을 출발하는 것입니다.

가희가 타고 있는 무궁화호의 x번째 이벤트가 hh_x:mm_x에 발생했고, x+1번째 이벤트가 hh_x+1:mm_x+1에 발생했다고 해 보겠습니다.

• 시각hh_x:mm_x이 시각 hh_x+1:mm_x+1보다 앞선다면, x번째 이벤트와 x+1번째 이벤트는 같은 날에 발생합니다.
• 그렇지 않으면 x번째 이벤트가 발생한 날 다음날에 x+1번째 이벤트가 발생합니다.

가희는 가희가 타고 있는 열차의 시간표를 보고, 특정 구간의 표정속도를 구하고 싶습니다. 가희를 도와주세요.

표정속도란, 일정 거리를 주행했을 경우 그 거리를 소요된 총 시간(주행 시간 + 정차 시간)으로 나누어 구한 속도를 의미합니다.

입력

첫 번째 줄에 가희가 타고 있는 열차의 정차역 개수 N과 가희의 질문 개수 Q가 주어집니다.

두 번째 줄부터 N개의 줄에 걸쳐서 정차역 이름과 도착 정보, 출발 정보가 공백을 구분으로 해서 주어집니다. 열차가 정차하는 순서대로 주어지며, 첫 번째로 주어지는 역은 시발역, 마지막으로 주어지는 역은 종착역입니다.

도착 정보와 출발 정보는 아래와 같이 주어집니다.

• 시발역 (열차가 운행을 시작하는 역)에 대한 도착 정보는 -:-로 주어집니다.
• 종착역 (열차가 운행을 종료하는 역)에 대한 출발 정보는 -:-로 주어집니다.
• 그 외에는 출발 정보와 도착 정보는 hh:mm 형식으로 주어집니다. hh:mm 형식은
  • hh는 0 이상 23 이하의 정수, mm은 0 이상 59 이하의 정수로 주어집니다. 만약, 한 자리 숫자면 앞에 0을 붙입니다.

N+2번째 줄부터 Q개의 줄에 걸쳐서 station₁과 station₂가 공백을 구분으로 해서 주어집니다.

이는 가희가 타고 간 열차의 운행 구간 station₁ ~ station₂의 표정속도(km/h)를 구하라는 의미입니다.

출력

Q개의 질문에 대한 답을 한 줄에 하나씩 출력해 주세요. 모범 답안과의 절대/상대 오차가 10^-6 이하인 경우 정답으로 인정됩니다.

제한

• 2 ≤ N ≤ 43
• 1 ≤ Q ≤ $\dfrac{N×(N-1)}{2}$
• 열차는 정차하는 모든 역에 대해 정시에 출발하고 정시에 도착합니다.
• 주어진 N개의 역은 모두 경부선에 있습니다.
• 열차가 시발역에서 종착역에 갈 때까지 소요 시간은 1시간 이상 6시간 이하입니다.
• 시발역과 종착역은 Seoul, Daejeon, Dongdaegu, Busan 중 하나이며, 시발역과 종착역이 같은 경우는 주어지지 않습니다.
• 열차의 시발역이 A이고 종착역이 B라고 했을 때
  • 열차가 중간에 방향을 바꾸는 일이 없습니다.
  • A에서 B로 갈 때 반드시 정차해야 하는 필수 정차역 (필수 정차 여부가 Y라고 표시된 역)이 누락되는 경우는 없습니다.
• 특정 구간의 표정속도를 구해야 하는 질문 station₁ station₂가 주어질 때
  • 가희가 타고 있는 열차가 정차하지 않는 역은 주어지지 않습니다.
  • 가희가 타고 있는 열차의 방향과 station₁에서 station₂로 향하는 방향은 같습니다.
  • 같은 역 2개가 주어지지 않습니다.
• 가희가 타고 있는 열차는 경부선 외에 다른 노선을 경유하지 않습니다.

노트