When Does C Pass M?

Time limit1sMemory limit128 MB

Summary
Given five observed meeting times along a highway, find the exact moment when car C passes car M.
Level

Medium6 of 10

Topics
Math, Implementation, Simulation, Brute force
Solved
No attempts yet

Problem

Three friends — Alecs (A), Celly (C), and Monny (M) — each drive a separate car from one city to another. At the same moment their mentor Dilbert (D) drives in the opposite direction, from the destination city back toward the starting city, to meet them along the way. Every car travels on the same straight highway, and each car moves at its own constant speed (the speeds need not be equal).

During the trip the following events are observed:

  • A passes C at time t1t_1 and passes M at time t2t_2.
  • A meets D (they are driving toward each other) at time t3t_3.
  • D meets C at time t4t_4 and meets M at time t5t_5.

All five times are distinct. Determine the exact time at which C passes M.

Because every car keeps a constant speed, each car's position is a linear function of time. Two cars 'pass' or 'meet' exactly when they are at the same position, so the answer is uniquely determined by the five given times.

Input

The input consists of several test cases, one per line. Each line contains five times t1t_1, t2t_2, t3t_3, t4t_4, and t5t_5, separated by whitespace and given in the hh:mm:ss format on a 24-hour clock. On each line the five times are distinct and listed in strictly increasing order. A line containing only -1 terminates the input and must not be processed.

Output

For each input line, print one line containing the time at which C passes M, in the same hh:mm:ss 24-hour format. Compute the exact time and round it to the nearest whole second, rounding an exact half-second up (for example, an exact 10:56:25.5 becomes 10:56:26).

Examples2

  1. Example 1

    Input
    10:00:00 11:00:00 12:00:00 13:00:00 14:00:00
    10:20:00 10:58:00 14:32:00 14:59:00 16:00:00
    10:20:00 12:58:00 14:32:00 14:59:00 16:00:00
    08:00:00 09:00:00 10:00:00 12:00:00 14:00:00
    -1
    
    Expected output
    12:00:00
    11:16:54
    13:37:32
    10:40:00
    
  2. Example 2

    Input
    06:00:00 06:30:00 07:00:00 07:30:00 08:00:00
    -1
    
    Expected output
    07:00:00