Alarm Clock

Interview

Time limit2sMemory limit256 MB

Summary

Print the earliest hh:mm time whose four digits use exactly n lit segments, or Impossible when no such time exists.

Level: Easy2 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

Alice likes her digital alarm clock and sets it every evening. Last night she dreamed about the clock. The only thing she remembers is how many segments were lit. Alice wants to know what time the clock showed in her dream.

The clock displays four digits. The first two are the hour and the last two are the minute, and a single digit value gets a leading zero. For example, half past nine reads 09:30.

Each digit is drawn with seven segments. The number of lit segments per digit is:

Digit	0	1	2	3	4	5	6	7	8	9
Lit segments	6	2	5	5	4	5	6	3	7	6

The colon between the hour and the minute does not count toward the number of lit segments.

Input

The first line contains the number of lit segments $n$ that Alice saw in her dream. ( $0 \le n \le 30$ )

Output

Print a time whose four digits use exactly $n$ lit segments, as five characters in "hh:mm" format. The time must satisfy $0 \le hh < 24$ and $0 \le mm < 60$ .

If several times satisfy the condition, print the earliest one, that is, the smallest "hh:mm" string in lexicographic order. If no time satisfies the condition, print Impossible.

Examples3

Example 1
Input
```
23
```
Expected output
```
00:02
```
Example 2
Input
```
28
```
Expected output
```
Impossible
```
Example 3
Input
```
2
```
Expected output
```
Impossible
```