Description

Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.

Given pairs of numbers A and B, output all the integers X such that A ≦ X ≦ B where X² is a palindrome; also print the value of that palindromic square. If there are no palindromes in the range, output -1 -1.

Input

Sample Input:

1 13
4 8

You can assume that A and B are non-negative integers no larger than 1,000 (i.e 0 ≦ A, B ≦ 1,000).

Output

Sample Output:

1 1
2 4
3 9
11 121
-1 -1

Approach

Read in the input range and generate all the numbers in that range. For each number, compute the square and convert that square integer into a string. Check if that string is a palindrome by scanning from the front and back of the string, towards the middle. As long as the characters match, we have a palindrome, otherwise, we don't. If we find a palindrome in a given range, output the original number and the square and set a flag. At the end of the range, if the flag is not set, output -1 -1.

Input/Output

• Final Input: problem001.input
• Final Output: problem001.output

Source Code

• Peter Bui's source code: pbui.c
• Noah Franske's source code: nfranske.c