URI Online Judge | 2681

Monkeys at Hanoi Tower

By Emilio Wuerges, UFFS BR Brazil

Time limit: 1

The Hanoi tower problem is very famous. However, very few people remember the original legend: It is sand that monkeys were tasked to solve the problem, and when they finish, the world ends.

The problem consists of 3 pins, and in the fist pin is sitting a stack of disks, one larger than the other. As we know, it is not allowed to place a larger disk above a smaller. This means that, to transfer one disk from the pile, one must first remove all the smaller ones first. Besides that, it is only allowed to move one disk at once.

The problem is solved when all disks from the first pin are transferred to the third pin.

We know that the monkeys started working at midnight (00:00:00), and that they work 24 hours per day, non stop, and they take at least 1 second to move each disk. Your task is to foresee the exact time of the day or night, in the format hh:mm:ss, of the earliest time possible the monkeys finish the game and the world ends.

Input

The input consists of a single line containing a single integer 0 < X < 1040, that is the number of disks in the starting stack.

Output

The output consists of a string in the format A:B:C, where 0 ≤ A < 24 e 0 ≤ B, C < 60

Exemplo de Entrada Exemplo de Saída

1

00:00:01

2

00:00:03

3

00:00:07

4

00:00:15