# 平方和球柱

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

魔法球依次编号为一、二、三，依此类推，每种编号恰好一个。你有若干根柱子，只有当新球与柱顶球的编号之和为完全平方数时，才能将它放到该柱顶；空柱可以直接放球。

## 形式化问题描述

给定柱子数 $N$ ，按 $1,2,3,\ldots$ 的顺序放球，不能跳过任何编号，也不能移动已经放好的球。每次选择一根空柱，或选择一根柱顶编号与新球编号之和为完全平方数的柱子，将新球放到顶端。

输出能够放入最多球数的任意一种最终方案。柱子有 $N$ 根，输出时按任意固定顺序逐根列出即可。

## 输入格式

一行一个整数 $N$ .

## 输出格式

输出 $N$ 行，第 $i$ 行按**从顶到底**的顺序列出第 $i$ 根柱子的所有球编号，用空格分隔。所有最优方案均接受。

## 样例

### 样例 1

### 输入

```text
4
```

### 输出

```text
8 1
11 5 4
9 7 2
10 6 3
```

### 样例 2

### 输入

```text
1
```

### 输出

```text
1
```

### 样例 3

### 输入

```text
3
```

### 输出

```text
5 4
6 3 1
7 2
```

## 样例解释

第一组放入编号一到十一。图中按从顶到底展示该最优方案；相邻两球编号之和均为完全平方数。再放入十二号球时，即使重新选择此前的放置方案，也无法用四根柱子完成。

![N=4; adjacent labels sum to 9, 16 or 4](assets/stacks.svg)

## 数据范围与保证

$1\le N\le1000$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |