AT_birthday0410_b ライスゲーム

**译者注：题目背景中的内容不影响对题意的理解，可以直接阅读题目描述部分。** 世界级的日本玩具制造商 Engrish 公司因业绩不佳而濒临破产。而如今，全球正掀起一股以大米为材料的“米饭游戏”空前热潮！Engrish 公司自然不愿错过这波风潮，决定全力进军日本市场。 要将这款游戏商品化并大规模生产，首先需要大量大米！项目负责人立刻联系海外分公司，说 **“更多大米（rice），拜托了！”** 然而…… “天啊……怎么会这样……” 几天后，总部收到的却是大量的虱子。面对数量惊人的虱子，员工们陷入绝望，负责人也哑口无言。为何会发生这种事？ 答案显而易见——负责人提出了 **“更多虱子（lice），拜托了！”** 的荒谬要求，让海外员工毫不犹豫地订购了大量虱子。换言之，负责人的发音酿成了这场惨剧。一切罪责都在负责人，公司并无过错。 背负巨额债务换来的大量虱子，如今无人知晓该如何处理。在这生死存亡之际，如果不能将这些虱子转化为收益，公司必将破产。 于是，Engrish 公司推出了“虱子游戏”。这是一款充分利用虱子的教育游戏，旨在让孩子们通过趣味方式学习生物生态。 游戏在划分为网格的培养玻璃板上进行。每个单元格存在有虱子和无虱子两种状态，第一天，你可以将虱子放在任何单元格中，之后每日按既定的规则逐日迭代。一个单元格明日是否存在虱子，取决于今日状态及其周边八个单元格的虱子数量，具体规则如下： - 今日有虱子的单元格：若周边虱子数为 $2$ 或 $3$ 个，则明日仍存在虱子（否则虱子消失） - 今日无虱子的单元格：若周边虱子数为 $3$ 个，则明日出现虱子（否则保持无虱子状态） 这款游戏理所当然地大获成功，Engrish 公司因此起死回生。 然而，有洁癖的 JAPLJ 屡屡发表“虱子太脏了，不要这么做”等伤害生物尊严的言论。好友 kyuridenamida 为让他更好、更正确地认识虱子，决定将虱子游戏作为生日礼物送给他。 虱子游戏的棘手之处在于：若随意布置虱子，可能导致其疯狂增殖，这对 JAPLJ 而言无异于噩梦。而且游戏被扔掉会立即被发现，因此绝对不能扔掉游戏。 觉察到危机的 JAPLJ 正制定对策。他想出了一个避免扔掉这个游戏的方法：在第一天布置虱子时，确保游戏在任何天数的状态都完全不变。 虱子游戏附带有固定数量的虱子，必须在第一天将所有虱子布置在网格上。由于收到游戏之前无法预知虱子的数量，JAPLJ 决定编写适用于任意虱子数量的程序。 作为 JAPLJ 的朋友，你需要协助完成这个程序。

显然，问题中的“虱子游戏”规则与康威生命游戏完全相同。因此需考虑无限网格上的生命游戏。 生命游戏中，无限网格上的每个细胞存在“生”或“死”两种状态。初始时设定若干个细胞为“生”细胞，其余细胞为“死”细胞。细胞的下一代状态由细胞的当前状态及周边八个细胞的状态决定。具体规则如下： - “生”细胞：若周边“生”细胞数为 $2$ 或 $3$ 个，则保持“生”（否则转为“死”） - “死”细胞：若周边“生”细胞数恰好为 $3$ 个，则转为“生”（否则保持“死”） 可参考维基百科生命游戏条目中的相同规则描述。 若一组“生”细胞配置中，任意“生”细胞均可通过在八个方向上相邻的“生”细胞到达其他“生”细胞，则称该配置为一个**八向连通配置**。 请编写程序，找出一个由 $N$ 个“生”细胞构成的八向连通配置，该配置需满足：经过任意次迭代后，配置完全不变（即初始 $N$ 个“生”细胞始终为“生”细胞，其余细胞始终为“死”细胞）。

> $N$ $N$ 表示“生”细胞的数量。

> $S_1$ > $S_2$ > $\dots$ > $S_N$ 对于正整数 $i$（$1\le i\le N$），$S_i$ 为一个长度为 $N$ 的字符串，表示细胞状态。这 $N$ 个字符串可以看作从无限网格中截取的 $N\times N$ 区域。 所有 $S_i$ 仅由 `.` 或 `#` 这两种字符组成，`.` 表示“死”细胞，`#` 表示“生”细胞。所有 $S_i$ 中 `#` 的总数必须恰好为 $N$，且所有 `#` 需构成一个八向连通配置。 若不存在满足条件的配置，则输出 `-1`。

**【数据范围】** - Subtask 1（1 分）：$1\le N \le 8$。 - Subtask 2（99 分）：无特殊限制。 对于全部数据，$1\le N \le 1000$。 **部分翻译由 Deepseek 生成。**