REVADD - Special Numbers (Reverse and Add)

A number $N$ is called special iff it can be written as $$ N = \mathrm{reverse}(N_1) + N_1 = \mathrm{reverse}(N_2) + N_2, $$ where $N_1$ and $N_2$ are some positive integers and their number of digits (lengths) are different.

For example, $121$ is a special number since $$ \begin{aligned} 121 &= \mathrm{reverse}(74) + 74 = \mathrm{reverse}(110) + 110 \\ &= 47 + 74 = 11 + 110. \end{aligned} $$

There are only two special number less than $10,000$.

Find the first 5,000 smallest special numbers.

Input

This problem has no input data.

Output

Output the first 5,000 special numbers in ascending order. (One special number per one line.)

Example

Output:
121
1111
...
[4998 lines]
...

Information

Source Limit is 10 KB.


Added by:Min_25
Date:2014-09-05
Time limit:3s
Source limit:10240B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2016-05-02 10:42:47 [Rampage] Blue.Mary
To debug the wrong program of this problem is a very challenging work...
2016-05-01 18:09:16 Min_25
@Amaterasu
Yes.
2016-05-01 15:01:51 Amaterasu
Is my understanding of problem statement correct: number k is special number IFF there exists at least 2 integers a and b such that a + reverse(a) == b + reverse(b) == k AND digitNum(a) != digitNum(b). Is that what you meant by "two distinct digit number"?
2014-10-21 08:23:24 S.Y.P.Lai
@Min_25
OK, I see. I'd made a false assumption. Those numbers are not special.
2014-10-21 08:23:24 Min_25
@S.Y.P.Lai
Please check special numbers (< 10^7) using a brute force approach.
2014-10-21 08:23:24 S.Y.P.Lai
@Min_25

Could you check the submissions with WAs? I think your standard solution has some errors.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.