有一个由 $$$n^2$$$ 顶点组成的图,其中顶点由整数对 $$$(r,c)$$$ 标记,使得 $$$1 \le r,c \le n$$$。顶点 $$$(r_1,c_1)$$$ 和 $$$(r_2,c_2)$$$ 是 直接 直接地 连接当且仅当 $$$(r_1-r_2)^2+(c_1-c_2)^2=\color{red}{13}$$$。该图称为 斑马图 尺寸为 $$$n \times n$$$。
请在维度为 $$$n \times n$$$ 的斑马图中找到满足以下条件的顶点子集 $$$S$$$。
- 由子集 $$$S$$$ 导出的图 $$$^{\text{∗}}$$$ 与至少 $$$\left\lfloor{\frac{n^2}{e}}\right\rfloor$$$ 顶点 $$$^{\text{†}}$$$ 的循环图同构。
可以证明,在该问题的约束下存在这样的顶点子集。
$$$^{\text{*}}$$$顶点子集$$$X$$$的导出图是包含$$$X$$$中的所有顶点以及两个端点都在$$$X$$$中的所有边的图。
$$$^{\text{†}}$$$这里,$$$e$$$ 是等于极限 $$$\lim \limits_{n \to \infty} \left ({1 + \frac{1}{n}} \right )^n \approx 2.71828182$$$ 的数学常数。请注意,$$$\frac{1}{e}$$$ 的值大约为 $$$0.36787944$$$。
输入
输入的第一行也是唯一一行包含单个整数 $$$n$$$ ($$$n\in \{5,1001\}$$$)。
此问题只有两个输入文件:
- 第一个输入文件(示例输入)有 $$$n=5$$$;
- 第二个输入文件有 $$$n=1001$$$。
对于此问题,黑客已被禁用。
输出
输出 $$$n$$$ 行,每行包含一个长度为 $$$n$$$ 的字符串 $$$s_i$$$ ,表示图形的第 $$$i$$$ 行。如果顶点 $$$(r,c)$$$ 是 $$$S$$$ 的元素,则 $$$s_r$$$ 的第 $$$c$$$ 个字母应该是 '1'。否则,$$$s_r$$$ 的第 $$$c$$$ 个字母应该是 '0'.
如果有多个解决方案,请打印其中任何一个。
示例
输入复制
5
输出复制
01110 11011 10001 11011 01110
注意
对于示例输出,与子集 $$$S$$$ 对应的归纳图如下所示。
该图与由 $$$16$$$ 顶点组成的循环图 $$$C_{16}$$$ 同构。由于 $$$16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$$$,输出满足问题的条件。