Массив \(a\) длины \(n\), пронумерованный с \(\mathbf{0}\), называется хорошим, если для всех корректных индексов \(i\) (\(0 \le i \le n-1\)) значение \(a_i + i\) является полным квадратом\(^\dagger\).
Дано целое число \(n\). Найдите перестановку\(^\ddagger\) \(p\) массива \([0,1,2,\ldots,n-1]\), являющуюся хорошим массивом, или определите, что такой перестановки не существует.
\(^\dagger\) Целое число \(x\) называется полным квадратом, если существует целое число \(y\) такое, что \(x = y^2\).
\(^\ddagger\) Массив \(b\) является перестановкой массива \(a\), если \(b\) состоит из элементов массива \(a\) в произвольном порядке. Например, \([4,2,3,4]\) является перестановкой \([3,2,4,4]\), а \([1,2,2]\) не является перестановкой \([1,2,3]\).
Выходные данные
Для каждого набора входных данных выведите \(n\) различных чисел \(p_0, p_1, \dots, p_{n-1}\) (\(0 \le p_i \le n-1\)) — перестановку \(p\) — если ответ существует, и \(-1\) иначе.
Примечание
В первом наборе входных данных \(n=3\). Массив \(p = [1, 0, 2]\) хороший, т. к. \(1 + 0 = 1^2\), \(0 + 1 = 1^2\) и \(2 + 2 = 2^2\)
Во втором наборе \(n=4\). Массив \(p = [0, 3, 2, 1]\) хороший, т. к. \(0 + 0 = 0^2\), \(3 + 1 = 2^2\), \(2+2 = 2^2\) и \(1+3 = 2^2\).