4899: [BJWC2018] 神奇的钟点

Memory Limit:512 MB Time Limit:10.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

一天,小 L 看到了 3 块钟表,分别显示着 01:0803:4013:52。小 L 发现,每块表上的时间都是 hh:mm 的形式,其中 hh 表示小时,mm 表示分钟,而且都不是整点(即 0hh<241mm<60)。

回想起小学数学老师刚刚讲的关于比例的知识,hh:mm 也表示一个比,它的值等于 hhmm。这时小 L 发现了一件神奇的事情:把这三个钟点加起来会得到 18:40,这也是一个不是整点的合法时间(注意小时数要小于 24),它对应的比值 920,与这三个钟点对应的比值 1834014 之和竟然相等!

现在小 L 想知道,把所有的满足这个神奇的性质的 3 个钟点组成的钟点组按照字典序排序后,第  小的是什么。

Input

输入仅包含一个正整数 

Output

输出字典序第  小的满足题目所述神奇性质的钟点组,以一个空格隔开,详见样例输出。如果答案不存在,输出 -1

Sample Input Copy

65432

Sample Output Copy

01:08 03:40 13:52

HINT

【样例说明】

注意钟点可以相同。

【数据规模和约定】

对于 30% 的数据,1000
对于 60% 的数据,20000
对于 100% 的数据,12×109