SQ2SQ - SQUARE TO SQUARE

no tags 

There are squares whose digits can be rearranged to make another squares. Lets call them S2S numbers.

for example: 144 → 441

Input

Single line containing two integers X Y (Xth, Yth term in the list of S2S numbers). Xth, Yth term<=10^12.

Output

Print all the numbers from Xth to Yth term of S2S numbers list (both inclusive).

Example

Input:
1 3

Output:
144
169
196

(Source Code Limit= 500B)
Note: 1 → 100 → 1 or other similar numbers are NOT S2S numbers (example 9 → 900 → 9)
Try Tutorial at http://www.spoj.com/problems/SQ2SQ2/


hide comments
caopeng: 2012-06-07 09:10:42

My solution of the tutorial version can be accepted at 5.xxs but got tle here....

caopeng: 2012-06-06 13:38:40

An algorithm using about O(10^7) is tle.... How can I do it without tle? I give every number a signiture....

Avinash: 2012-05-24 14:41:23

@zukow..its all about time limit.

:D: 2012-05-24 06:13:23

Thanks. Nice problem, I thought code limit was tight, but with proper algo and basic code golfing it should be easy to fit.

Mitch Schwartz: 2012-05-23 21:20:41

That's right.

:D: 2012-05-23 06:26:36

10^12 is the limit for square values, not indexes, right?


Added by:Avinash
Date:2012-04-11
Time limit:0.100s-2.029s
Source limit:500B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem