Organize Books

You are given a list of book identifiers. Your task is to reorganize the list so that:

• All identifiers that are perfect squares (i.e. numbers of the form \(n^2\) for some integer \(n\)) appear first in the same order as they were in the input.
• The remaining identifiers are sorted in ascending order and come after the perfect squares.

For example, given the list [16, 3, 4, 10, 25, 2]:

• The perfect squares are 16, 4, and 25 (in the original order).
• The non-perfect squares are [3, 10, 2] which when sorted in ascending order become [2, 3, 10].

The final output is: [16, 4, 25, 2, 3, 10].

inputFormat

The first line of input contains a single integer \(n\) indicating the number of book identifiers.

The second line contains \(n\) space-separated integers representing the book identifiers.

outputFormat

Output the reorganized list of book identifiers in a single line, separated by spaces.

5
16 4 9 25 36

16 4 9 25 36