[BJWC2018] 神奇的钟点

题目描述

一天,小 L 看到了 3 块钟表,分别显示着 $\texttt{01:08}$、$\texttt{03:40}$、$\texttt{13:52}$。小 L 发现,每块表上的时间都是 $\texttt{hh:mm}$ 的形式,其中 $\texttt{hh}$ 表示小时,$\texttt{mm}$ 表示分钟,而且都不是整点(即 $0\leqslant\texttt{hh}<24$,$1\leqslant\texttt{mm}<60$)。 回想起小学数学老师刚刚讲的关于比例的知识,$\texttt{hh:mm}$ 也表示一个比,它的值等于 $\frac{\texttt{hh}}{\texttt{mm}}$。这时小 L 发现了一件神奇的事情:把这三个钟点加起来会得到 $\texttt{18:40}$,这也是一个不是整点的合法时间(注意小时数要小于 $24$),它对应的比值 $\frac{9}{20}$,与这三个钟点对应的比值 $\frac{1}{8}$、$\frac{3}{40}$、$\frac{1}{4}$ 之和竟然相等! 现在小 L 想知道,把所有的满足这个神奇的性质的 3 个钟点组成的钟点组按照字典序排序后,第 $k$ 小的是什么。

输入输出格式

输入格式


输入仅包含一个正整数 $k$。

输出格式


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

输入输出样例

输入样例 #1

65432

输出样例 #1

01:08 03:40 13:52

输入样例 #2

1

输出样例 #2

00:01 00:01 00:01

输入样例 #3

58

输出样例 #3

00:01 00:02 00:01

输入样例 #4

2000000000

输出样例 #4

-1

说明

**【样例说明】** 注意钟点可以相同。 **【数据规模和约定】** 对于 $30\%$ 的数据,$k\leqslant 1000$。 对于 $60\%$ 的数据,$k\leqslant 20000$。 对于 $100\%$ 的数据,$1\leqslant k\leqslant 2\times 10^9$。