Bài 2

Cho một xâu $S$ chỉ gồm các ký tự chữ cái trong bảng chữ cái tiếng Anh và các chữ số từ 0 đến 9. Một số trong xâu $S$ được định nghĩa là một ký tự chữ số hoặc là các kí tự số liên tiếp và không bao gồm các chữ số 0 không có nghĩa.

Ví dụ với xâu $S =$ "05aAb21bc3956cDe488a" các số có trong xâu là $5$, $21$, $3956$, $488$.

Yêu cầu: Cho xâu $S$ chỉ gồm các kí tự chữ cái tiếng Anh và các chữ số. Hãy viết chương trình tìm số chính phương lớn nhất có trong xâu $S$.

(Số chính phương là số bằng bình phương của một số nguyên, ví dụ $9$ là số chính phương vì $9 = 3^2$).

• Dữ liệu vào gồm xâu $S$ chỉ chứa các ký tự chữ cái trong bảng chữ cái tiếng Anh và chữ số.

• In ra số chính phương lớn nhất tìm được hoặc số $-1$ nếu không tìm được số chính phương nào.

• Độ dài xâu không quá $10^5$ ký tự.
• Dữ liệu đảm bảo xâu $S$ có không quá $18$ chữ số có nghĩa liền nhau.

Chấm điểm:

• Subtask $1$ ($30\%$ số điểm): xâu $S$ có độ dài không quá $250$ ký tự.
• Subtask $2$ ($30\%$ số điểm): xâu $S$ có độ dài không quá $10^3$ ký tự.
• Subtask $3$ ($40\%$ số điểm): theo dữ liệu đề bài.