平方和球柱¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
魔法球依次编号为一、二、三，依此类推，每种编号恰好一个。你有若干根柱子，只有当新球与柱顶球的编号之和为完全平方数时，才能将它放到该柱顶；空柱可以直接放球。
形式化问题描述¶
给定柱子数 \(N\) ，按 \(1,2,3,\ldots\) 的顺序放球，不能跳过任何编号，也不能移动已经放好的球。每次选择一根空柱，或选择一根柱顶编号与新球编号之和为完全平方数的柱子，将新球放到顶端。
输出能够放入最多球数的任意一种最终方案。柱子有 \(N\) 根，输出时按任意固定顺序逐根列出即可。
输入格式¶
一行一个整数 \(N\) .
输出格式¶
输出 \(N\) 行，第 \(i\) 行按从顶到底的顺序列出第 \(i\) 根柱子的所有球编号，用空格分隔。所有最优方案均接受。
样例¶
样例 1¶
输入¶
4
输出¶
8 1
11 5 4
9 7 2
10 6 3
样例 2¶
输入¶
1
输出¶
1
样例 3¶
输入¶
3
输出¶
5 4
6 3 1
7 2
样例解释¶
第一组放入编号一到十一。图中按从顶到底展示该最优方案；相邻两球编号之和均为完全平方数。再放入十二号球时，即使重新选择此前的放置方案，也无法用四根柱子完成。
数据范围与保证¶
\(1\le N\le1000\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |