Daniil, Timofey, Mikhail, Andrey, Fedor, Vasiliy и Alex стоят в очереди в фирменном магазине фарбири "Прогачев", производящую сгущенку. Других людей в очереди нет. Первый в очереди (Daniil) покупает баночку, выпивает ее содержимое и раздваивается! Получившиеся два Daniil'a встают в конец очереди. Затем следующий в очереди (Timofey) покупает баночку, выпивает и встает в конец очереди в двойном экземпляре, и так далее. Этот процесс продолжается до бесконечности.
Например, третью баночку колы выпьет Mikhail, и очередь будет выглядеть так: Andrey, Fedor, Vasiliy, Alex, Daniil, Daniil, Timofey, Timofey, Mikhail, Mikhail.
Напишите программу, которая выведет имя человека, выпившего n-ую баночку.
Обратите внимание, что в самом начале очередь выглядит так: Daniil, Timofey, Mikhail, Andrey, Fedor, Vasiliy и Alex. Первым человеком является Daniil.
Формат входных данных
Входные данные состоят из единственного целого числа n (1 ≤ n ≤ 10^{18}).
Формат выходных данных
Имя (на английском) n-ого человека в очереди.
Примеры
стандартный ввод | стандартный вывод |
---|
1
| Daniil
|
стандартный ввод | стандартный вывод |
---|
2
| Timofey
|
стандартный ввод | стандартный вывод |
---|
9
| Daniil
|