Description

One day, Xiao L saw three clocks showing $\texttt{01:08}$, $\texttt{03:40}$, and $\texttt{13:52}$. Xiao L noticed that each time is in the form $\texttt{hh:mm}$, where $\texttt{hh}$ is the hour and $\texttt{mm}$ is the minute, and none of them is on the hour (i.e., $0\leqslant\texttt{hh}<24$, $1\leqslant\texttt{mm}<60$).

Recalling a lesson about ratios, $\texttt{hh:mm}$ also represents a ratio with value $\frac{\texttt{hh}}{\texttt{mm}}$. Then Xiao L discovered something magical: adding these three times yields $\texttt{18:40}$, which is also a valid time that is not on the hour (note the hour must be less than $24$). Its corresponding ratio $\frac{9}{20}$ is exactly equal to the sum of the ratios $\frac{1}{8}$, $\frac{3}{40}$, and $\frac{1}{4}$ of the three times!

Now Xiao L wants to know: among all triplets of times that satisfy this magical property, sorted in lexicographic order, what is the $k$-th smallest?

Input Format

The input contains only a single positive integer $k$.

Output Format

Output the $k$-th smallest triplet that satisfies the magical property described in the statement, with the three times separated by a space; see the sample output. If the answer does not exist, output -1.

65432

01:08 03:40 13:52

1

00:01 00:01 00:01

58

00:01 00:02 00:01

2000000000

-1

Hint

【Sample Explanation】

Note that the times may be identical.

【Constraints】

For $30\%$ of the testdata, $k\leqslant 1000$.
For $60\%$ of the testdata, $k\leqslant 20000$.
For $100\%$ of the testdata, $1\leqslant k\leqslant 2\times 10^9$.

Translated by ChatGPT 5