1305 - 二进制手表

通过次数

6

提交次数

13

Time Limit : 1 秒
Memory Limit : 128 MB

二进制手表顶部有 4 个 LED 代表 小时(0-11),底部的 6 个 LED 代表 分钟(0-59)。每个 LED 代表一个 0 或 1,最低位在右侧。

  • 例如,下面的二进制手表读取 "3:25"

https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/29/binary_clock_samui_moon.jpg

给你一个整数 turnedOn ,表示当前亮着的 LED 的数量,返回二进制手表可以表示的所有可能时间。

小时不会以零开头:

  • 例如,"01:00" 是无效的时间,正确的写法应该是 "1:00"

分钟必须由两位数组成,可能会以零开头:

  • 例如,"10:2" 是无效的时间,正确的写法应该是 "10:02"

Input

一个整数

Output

所有可能的时间

Examples

Input

1

Output

1:00
2:00
4:00
8:00
0:01
0:02
0:04
0:08
0:16
0:32

Input

9

Output


                                

Hint

  • 0 <= turnedOn <= 10