Lucky-number Sum

Time limit2sMemory limit128 MB

Summary

Given N, express it as a sum of numbers made only of digits 4 and 7, using the fewest terms and, among ties, the lexicographically smallest sequence.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Math, Combinatorics
Solved: No attempts yet

Problem

Eunmin likes the digits 4 and 7, and dislikes every other digit. A lucky number is a positive integer written using only the digits 4 and 7.

Given an integer N, write N as a sum of lucky numbers. If several representations are possible, output one that uses the fewest numbers. If there is still more than one such representation, output the lexicographically smallest sequence.

For two representations with the same number of terms,

N = a1 + a2 + ... + ak

comes before

N = b1 + b2 + ... + bk

if, at the first index i where ai and bi differ, ai < bi. If N cannot be represented as a sum of lucky numbers, output -1.

Input

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

Output

Print the answer on one line, with numbers separated by spaces.

Examples4

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