题目描述

要用多少种颜色给整个平面染色，才能使任意两个距离为 $1$ 的点颜色不同？令人惊讶的是，目前只知道答案是 $5,6,7$ 中的一个，但并不知道究竟是哪一个。这个问题被称为 Hadwiger-Nelson 问题。

本题考虑 Hadwiger-Nelson 问题的一个有限且离散化的变体。

需要给一个 $N\times N$ 网格中的方格染色，目标是使用尽可能少的颜色，并满足：任意两个被染色的点，如果它们之间的距离恰好为

则它们必须颜色不同。

只给每个方格的内部染色；方格的边和角不染色。这意味着，例如当 $R=2$ 时，方格 $(1,1)$ 和 $(1,4)$ 可以染成相同颜色，尽管第一个方格的右下角与第二个方格的左下角之间的距离恰好为 $2$。

输入格式

输入仅一行，包含三个整数 $N,P,Q$。

在所有用于评分的测试中，都有 $N=50$。

输出格式

输出 $N$ 行，每行 $N$ 个整数，表示方格的染色方案。

颜色用整数 $1,2,\ldots,N^2$ 表示。

样例

输入

4 3 1

输出

2 2 7 7
2 5 5 7
1 5 5 3
1 1 3 3

样例解释

该方案使用了 5 种颜色，虽然这个样例也可以用 4 种颜色解决。

此处有一张网格示意图，展示从一个蓝色点出发，距离为 3 的若干点必须染成其他颜色。】

图中展示了与某个蓝色点距离为 3 的点，这些点都必须使用其他颜色。具体来说，标出的点 $(0.7,0.6)$ 是蓝色；距离它为 3 的一个点近似为 $(3.506,1.661)$，该点是绿色，因此不是蓝色。

这里使用的坐标系中，第一坐标轴从左到右，第二坐标轴从下到上，网格左下角坐标为 $(0,0)$。

数据范围与评分

对于所有数据：

在所有评分测试中：

本题通过测试环境给出 20 个输入文件 input_001.txt 到 input_020.txt，参赛者需要提交对应的输出文件 output_001.txt 到 output_020.txt。不需要提交程序，程序也不会被评分。

每个测试点价值 5 分。如果染色方案不满足题目条件，则该测试点总是得到 0 分。

若方案合法，并且使用了 $K$ 种不同颜色，则该测试点得分为：

其中 $M$ 是所有参赛者在该测试点上提交的合法方案中使用颜色数的最小值。

换句话说，一个方案比最优合法方案分别多使用 $0,1,2,\ldots$ 种颜色时，该测试点得分分别为 $5,2.5,1.25,\ldots$ 分。

下发文件