Sum of Lucky Numbers

Time limit2sMemory limit128 MB

Summary

Write N as a sum of the fewest numbers made only of digits 4 and 7, breaking ties by the lexicographically smallest sequence.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Math, Backtracking
Solved: No attempts yet

Problem

Eunmin likes only the digits 4 and 7. A lucky number is a positive integer whose decimal representation consists only of 4 and 7.

Given an integer N, represent N as a sum of one or more lucky numbers. If multiple representations exist, output one that uses the fewest numbers. If there is still more than one such representation, output the lexicographically smallest sequence when compared from left to right. If N cannot be represented, output -1.

For two representations N = a1 + a2 + ... + ak and N = b1 + b2 + ... + bk, the first representation is earlier if, at the smallest index i where ai and bi differ, ai < bi.

Input

The first line contains N. N is at most 1,000,000.

Output

Print the answer on the first line, separating numbers with spaces.

Examples4

Example 1
Input
```
11
```
Expected output
```
4 7
```
Example 2
Input
```
12
```
Expected output
```
4 4 4
```
Example 3
Input
```
13
```
Expected output
```
-1
```
Example 4
Input
```
100
```
Expected output
```
4 4 4 44 44
```