CF1775F Laboratory on Pluto

如你所知，火星科学家们正在积极进行太空研究。其中最重要的任务之一就是对冥王星的研究。为了更详细地研究这颗行星，决定在冥王星上建造一个实验室。 已知实验室将由 $n$ 个大小相同的正方形模块搭建而成。为方便起见，我们假设冥王星的表面是一个被水平和垂直线划分成单位正方形的平面。每个正方形要么被实验室模块占据，要么为空，且恰好有 $n$ 个正方形被占据。 由于每个模块都是正方形，因此它有四面墙。如果某面墙与另一个模块相邻，则该墙被视为内部墙，否则为外部墙。 冥王星以极端寒冷著称，因此实验室的外部墙必须进行隔热。每一单位外部墙需要一单位隔热材料。因此，实验室外部墙的总长度（即其周长）越大，所需的隔热材料就越多。 请考虑下图中的实验室布局。图中实验室由 $n=33$ 个模块组成，所有模块共有 $24$ 个外部墙面，即需要 $24$ 单位的隔热材料。 你需要以最优方式搭建实验室，即使所需隔热材料最少。另一方面，可能存在多种最优方案，因此科学家们还关心在最优隔热材料用量下，有多少种不同的搭建方式（对一个质数 $m$ 取模）。 如果两个方案在重叠后完全一致（不允许旋转），则视为同一种方案。因此，如果一个实验室布局旋转 $90^\circ$，则可视为另一种不同的方案。 为了帮助科学家们探索冥王星，你需要编写程序解决这些难题。 

第一行包含两个整数 $t$ 和 $u$（$1 \le t \le 2\cdot 10^5$，$1 \le u \le 2$），分别表示测试用例数量和测试类型。如果 $u=1$，你需要输出一种最优搭建实验室的方式；如果 $u=2$，你需要计算最优搭建方式的数量。 如果 $u=2$，则输入的下一行包含一个质数 $m$（$10^8 \le m \le 10^9 + 9$），你需要对 $m$ 取模输出方案数。 接下来的 $t$ 行，每行一个整数 $n$（$1 \le n \le 4\cdot 10^5$），表示实验室应由多少个模块组成。 保证如果 $u=1$，所有测试用例中 $n$ 的总和不超过 $8\cdot10^5$。

对于每个测试用例，按下述格式输出答案，每个答案之间用换行分隔。输出格式取决于输入数据中的 $u$。 如果 $u=1$，第一行输出两个整数 $h$ 和 $w$，表示实验室搭建区域的高度和宽度。接下来的 $h$ 行，每行输出一个由 $w$ 个字符组成的字符串 $s_i$，每个字符为“#”或“.”。如果第 $j$ 个字符为“#”，则对应位置放置一个实验室模块，否则为空。这样得到一个字符矩阵。还需满足：矩阵的首行和末行、首列和末列都至少有一个“#”，否则可以输出更小的 $h$ 和 $w$。 如果存在多种最优搭建方式，你可以输出任意一种。 如果 $u=2$，输出两个整数 $p$ 和 $c$，分别表示最优实验室的外部墙数量，以及方案数对质数 $m$ 取模后的结果。

请考虑第二个示例。 如果 $n=1$，唯一的搭建方式是放置一个模块，此时周长为 $4$。 当 $n=2$ 时，必须将两个模块相邻放置，可以竖直或水平排列，因此有两种方式。此时实验室的外部墙总数为 $6$。 对于 $n=7$，下图展示了所有 $22$ 种最优方案。  由 ChatGPT 4.1 翻译