Warning:

This is a typical problem.

You can find the answer online and output it directly, but I don't recommend you to do so. You can also find the script anywhere, paste it and submit it, but I don't recommend you to do so either.

(Actually, I can't prevent you from doing this, but I hope you take responsibility for yourself.)

Background

Hereafter, stars will shine because I have come.

Hereafter, flowers will bloom because I have never left.

Blooming flowers and shining stars are always synonymous with people's longing for beauty, so when people discover beauty in life, they always name it after flowers and stars.

While learning computer programming, Mr. Sha accidentally discovered a special number: $153$. It is special in that as a $3$-digit number, the sum of the $3$rd powers of the digits on each digit is equal to itself ($1^3+5^3+3^3=1+125+27=153$). And after further research by Mr. Sha, he found that there are many digits in decimal system whose sum of powers $n$ is equal to its own $n$-digit positive integer.

Mr. Sha thought this property is too beautiful, so he named all numbers that satisfy this property with beautiful flowers and stars, such as: such $3$-digit numbers are called narcissus numbers, such $4$-digit numbers are called clover numbers, such $5$-digit numbers are called pentagram numbers, such $7$-digit numbers are called Big Dipper numbers, etc.

Description

Mr. Sha wants to use a program to find that the sum of the $n$-th powers of all digits in the decimal system is equal to its own $n$-digit positive integer. Could you please help him write this program?

Format

Input

An integers $n$, satisfying $1\leq n\leq 7$ .

Output

All $n$-digit positive integers that meet the criteria (arranged in ascending order, separated by spaces). If there are no numbers that meet the conditions, output $-1$.

Samples

1

1 2 3 4 5 6 7 8 9

3

153 370 ... ...
(The remaining part will not be displayed)

Hint

If a language works slowly, try another.

Please weave my arrow, my flower, and my love into the seeds of new life, and bring them to the withered earth. Then let them blossom into eternal and flawless... the flowers of humanity.

Limitation

1s, 1024KiB for each test case.