피카파우스
면접 대비시간 제한2초메모리 제한1024 MB
두 사람이 연속한 목적지 사이를 일정한 속도로 이동할 때, 두 사람 사이 거리가 가장 작아지는 시각을 구한다.
문제
많은 문화권에서 근무일 중간중간에는 휴식이 들어간다. 이런 휴식은 근로자가 쉬게 해 주어 생산성을 높일 수 있다. 어떤 사람은 물을 마시고, 어떤 사람은 커피를 마시며, 또 어떤 사람은 간식을 먹거나 책을 읽거나 산책을 하거나 다른 사람과 이야기를 나눈다. 스웨덴에서는 커피 휴식이 인기 있으며 이를 "피카파우스"라고 부른다.
당신이 스웨덴에서 일하고 있고, 동료와 함께 하루에 한 번 피카파우스를 즐기고 싶다고 하자. 두 사람의 업무상 하루 종일 도시 곳곳을 각자 따로 이동해야 한다. 이동 계획이 매일 바뀌기 때문에 피카파우스를 하기에 가장 좋은 시각은 날마다 다르다. 하지만 두 사람은 자신의 이동 일정을 미리 알고 있고, 두 사람이 가장 가까이 있는 시각에 만나기로 계획할 수 있다. 피카파우스를 하기에 가장 좋은 시각을 구하는 프로그램을 작성하라.
입력
입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 하루 동안의 당신과 동료의 이동 일정을 나타낸다. 이동 일정은 당신과 동료가 각각 방문할 목적지의 수를 나타내는 정수 1 ≤ D ≤ 20으로 시작한다. 이어서 D개의 시각과 목적지 쌍이 M X1 Y1 X2 Y2 형식으로 주어진다. 정수 0 ≤ M ≤ 500은 오전 9시 이후 M분에 당신이 도시의 좌표 X1, Y1에 있고 동료가 좌표 X2, Y2에 있음을 나타낸다. 모든 좌표는 0 이상 1000 이하의 정수이다. 각 테스트 케이스에서 M 값은 모두 서로 다르며 증가하는 순서로 주어진다. 마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 온다.
출력
각 테스트 케이스마다 케이스 번호(1부터 시작)에 이어 두 사람이 가장 가까이 있는 시각(오전 9시 이후 분)을 출력한다. 두 점 사이의 거리는 두 점이 정의하는 선분의 길이로 잰다. 두 사람이 가장 가까이 있는 시각이 여러 개라면 가장 이른 시각을 보고한다. 출력 형식은 예시 출력을 따르라.