This page is still under construction.

Parts of this page are still being built. What you see may change.

Clock

Interview

Time limit1sMemory limit128 MB

Summary
Find the time with the median clock-hand angle among five given times, breaking angle ties by earlier time.
Level

Easy2 of 10

Topics
Math, Sorting, Implementation
Solved
No attempts yet

Problem

Kiwon's room has an analog clock with an hour hand and a minute hand. Kiwon enjoys measuring the smaller of the two angles formed by the hour and minute hands; this angle is always between 0 and 180 degrees, inclusive.

Given five distinct times in hh:mm format, we want to compute the smaller angle formed by each time's hour and minute hands, then find the time whose angle is the median (the third smallest of the five).

In other words, sort the five times in ascending order of angle and output the one in the third position. If several times share the same angle, order them so that the earlier time of day (the one with the smaller value when hh:mm is converted to minutes) comes first.

For example, given 06:05, 07:10, 03:00, 21:00, 12:55, sorting by angle gives 12:55, 03:00, 21:00, 06:05, 07:10, so the time in the third position (the median) is 21:00.

Help Kiwon by writing a program that finds the time with the median angle among the given times.

Input

The first line contains the number of test cases TT.

Each test case consists of five distinct times in hh:mm format, separated by a single space.

Each time satisfies 00≤hh≤2300 \le hh \le 23 and 00≤mm≤5900 \le mm \le 59.

Output

For each test case, print the time whose angle is the median, in hh:mm format, one per line.

Examples1

  1. Example 1

    Input
    3
    00:00 01:00 02:00 03:00 04:00
    06:05 07:10 03:00 21:00 12:55
    11:05 12:05 13:05 14:05 15:05
    
    Expected output
    02:00
    21:00
    14:05