[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$。