Description

Xiaoming found that $49$ is very interesting. First, it is a square number. It can be split into $4$ and $9$, and the parts after splitting are also square numbers. $169$ also has this property. For convenience, we call such numbers: concatenated square numbers.

$100$ can be split into $1,00$, which is a bit forced. We define that $0,00,000$, etc. are not considered square numbers.

Xiaoming wonders: what other numbers are like this?

Your task is: find all concatenated square numbers within a given interval.

Input Format

Two positive integers $a,b(a<b<10^6)$.

Output Format

Output several lines, one positive integer per line. Print all concatenated square numbers in the interval $[a,b]$, in increasing order.

169 10000

169
361
1225
1444
1681
3249
4225
4900
9025

Hint

Time limit: 1 second, 256M. The 5th Lanqiao Cup 2014 National Finals.

Translated by ChatGPT 5