题目描述

输入一个正整数序列\(\{a_i\}, i=1,2 \cdots N\)，按照如下规则排序：
（1） 完全平方数放在前边，其他数放在后边；
（2） 在（1）的基础上，数值小的放前边，数值大的放后边。
输出按上述规则排序后的结果。

I/O格式

输入

第一行是一个正整数\(N\)；
第二行是\(N\)个正整数\(a_1, a_2 \cdots a_N\)。
\(N \le 10^5, a_i \le 10^9\)

输出

输出一行，原序列排序后的结果，每两个数之间用一个空格隔开。

样例

输入

6
2 9 5 4 13 37

输出

4 9 2 5 13 37

时空限制

1s, 64MB。

提示

利用以下的is_perfect_square可以快速判断一个数是否为完全平方数：（需要包含头文件<cmath>）

//截取小数部分并判断其是否为零（考虑到浮点数误差，故将小数部分<1e-8作为判断条件）
bool is_perfect_square(int x)
{
    double s = fmod(sqrt(x), 1.0);
    //return s < 1e-8;
     return s < 1e-8 || s > 1.0 - 1e-8;
}