Holy Grail

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

King Arthur and the brave knights of the Round Table are looking for the legendary Holy Grail. They arrive at the Bridge of Death where they are met by the old man from Scene 24. The old man asks them three questions. If they answer correctly, he lets them pass, otherwise they fall into eternal doom. After a few failed attempts by the brave knights, Arthur approaches the old man.

  • Old man: What is your name?
  • Arthur: I am Arthur, the king of Britain.
  • Old man: What it your quest?
  • Arthur: To find the Holy Grail!
  • Old man: Let n be an integer. If we take an integer x and add all its digits to x we obtain n. How many such numbers x are there and what are those numbers?

Arthur is not able to answer the third question and he needs your help. Write a program that finds all such numbers.

Task

Let n be an integer. We are looking for integers x, so that the sum of x and all of its digits equals n. Find all such integers x and print them.

Input

The only line of the input contains the integer n.

Input limits

  • 1 \leq n \leq 10^9

Output

The first line should contain the number of solutions. Each of the following lines should contain one solution (sorted in ascending order).

Examples

Input

21

Output

1
15

Input

20

Output

0

Comment

In the first example, there is only one such solution, i.e. 15 + 1 + 5 = 21. In the second example, no solution exists.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task