Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

This round has an unusual addition to the rules. For each problem you must use distinct language. Thus, if you have a submission that has passed at least one test or is being tested at the moment, then for this task you can use only this language and can not use it for other tasks. More details can be read by the link. Different implementations of the same language are considered to be the same language (for example, in C++ you can only solve one problem, regardless of the exact chosen compiler).

No tag edit access

I. A Vital Problem

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp has a strict daily schedule. He has *n* alarms set for each day, and the *i*-th alarm rings each day at the same time during exactly one minute.

Determine the longest time segment when Polycarp can sleep, i. e. no alarm rings in that period. It is possible that Polycarp begins to sleep in one day, and wakes up in another.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 100) — the number of alarms.

Each of the next *n* lines contains a description of one alarm. Each description has a format "hh:mm", where *hh* is the hour when the alarm rings, and *mm* is the minute of that hour when the alarm rings. The number of hours is between 0 and 23, and the number of minutes is between 0 and 59. All alarm times are distinct. The order of the alarms is arbitrary.

Each alarm starts ringing in the beginning of the corresponding minute and rings for exactly one minute (i. e. stops ringing in the beginning of the next minute). Polycarp can start sleeping instantly when no alarm is ringing, and he wakes up at the moment when some alarm starts ringing.

Output

Print a line in format "hh:mm", denoting the maximum time Polycarp can sleep continuously. *hh* denotes the number of hours, and *mm* denotes the number of minutes. The number of minutes should be between 0 and 59. Look through examples to understand the format better.

Examples

Input

1

05:43

Output

23:59

Input

4

22:00

03:21

16:03

09:59

Output

06:37

Note

In the first example there is only one alarm which rings during one minute of a day, and then rings again on the next day, 23 hours and 59 minutes later. Polycarp can sleep all this time.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:37:04 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|