가희와 무궁화호

문제

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


역 번호	역 이름	거리(km)	필수 정차 여부	역 번호	역 이름	거리(km)	필수 정차 여부
1	Seoul	0.0	Y	23	Chupungnyeong	234.7	N
2	Yeongdeungpo	9.1	Y	24	Gimcheon	253.8	Y
3	Anyang	23.9	N	25	Gumi	276.7	Y
4	Suwon	41.5	Y	26	Sagok	281.3	N
5	Osan	56.5	N	27	Yangmok	289.5	N
6	Seojeongri	66.5	N	28	Waegwan	296.0	Y
7	Pyeongtaek	75.0	Y	29	Sindong	305.9	N
8	Seonghwan	84.4	N	30	Daegu	323.1	Y
9	Cheonan	96.6	Y	31	Dongdaegu	326.3	Y
10	Sojeongni	107.4	N	32	Gyeongsan	338.6	N
11	Jeonui	114.9	N	33	Namseonghyeon	353.1	N
12	Jochiwon	129.3	Y	34	Cheongdo	361.8	N
13	Bugang	139.8	N	35	Sangdong	372.2	N
14	Sintanjin	151.9	N	36	Miryang	381.6	Y
15	Daejeon	166.3	Y	37	Samnangjin	394.1	N
16	Okcheon	182.5	N	38	Wondong	403.2	N
17	Iwon	190.8	N	39	Mulgeum	412.4	N
18	Jitan	196.4	N	40	Hwamyeong	421.8	N
19	Simcheon	200.8	N	41	Gupo	425.2	Y
20	Gakgye	204.6	N	42	Sasang	430.3	N
21	Yeongdong	211.6	Y	43	Busan	441.7	Y
22	Hwanggan	226.2	N

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

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

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

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

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

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

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


순번	역 이름	순번	역 이름
1	Seoul	10	Gumi
2	Yeongdeungpo	11	Waegwan
3	Suwon	12	Daegu
4	Pyeongtaek	13	Dongdaegu
5	Cheonan	14	Gyeongsan
6	Jochiwon	15	Cheongdo
7	Daejeon	16	Miryang
8	Yeongdong	17	Gupo
9	Gimcheon	18	Busan

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

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

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

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

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

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

입력

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

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

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

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

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

이는 가희가 타고 간 열차의 운행 구간 station1 ~ station2의 표정속도(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라고 표시된 역)이 누락되는 경우는 없습니다.
특정 구간의 표정속도를 구해야 하는 질문 station1 station2가 주어질 때
- 가희가 타고 있는 열차가 정차하지 않는 역은 주어지지 않습니다.
- 가희가 타고 있는 열차의 방향과 station1에서 station2로 향하는 방향은 같습니다.
- 같은 역 2개가 주어지지 않습니다.
가희가 타고 있는 열차는 경부선 외에 다른 노선을 경유하지 않습니다.