如您所知,火星科学家正在积极从事太空研究。最优先考虑的事情之一是冥王星。为了更详细地研究这颗行星,决定在冥王星上建立一个实验室。
众所周知,实验室将由 $$$n$$$ 大小相等的方块建造。为了方便起见,我们假设冥王星的表面是一个被垂直线和水平线划分为单位正方形的平面。每个方格要么被实验室块占据,要么不被占据,并且只有 $$$n$$$ 方格被占据。
由于每个街区都是方形的,因此它有四堵墙。如果一堵墙与另一个街区相邻,则它被视为在内部,否则被视为在外部。
冥王星以其极冷的温度而闻名,因此实验室的外墙必须隔热。每面外墙需要一个单位的隔热层。因此,实验室外墙的总长度(即其周长)越大,需要的隔热材料就越多。
考虑下图中的实验室布局。它显示实验室由 $$$n = 33$$$ 块组成,所有块的外墙总数为 $$$24$$$,即。 e.需要 $$$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$$$),对其取模,您需要计算路数。
以下输入的每一行 $$$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$$$。如果$$$s_i$$$行的第$$$j$$$个字符是“#”,则对应的方格必须包含实验室块,否则被认为是空的。这样,我们就得到了一个符号矩阵。还必须满足条件,即矩阵的第一行和最后一行以及第一列和最后一列必须至少有一个字符“#”,否则我们可以输出相同的实验室布局,但 $$$h$$$ 和 $$$w$$$ 较小。如果构建最佳实验室有多种选择,您可以打印其中任何一个。
如果$$$u=2$$$,则需要打印两个整数$$$p$$$和$$$c$$$——最佳实验室的外墙数量,以及以素数模$$$m$$$得到的路数的余数。
示例
输入 #1
3 1 1 2 7
输出 #1
1 1 # 1 2 ## 2 4 .### ####
输入 #2
3 2 1000000007 1 2 7
输出 #2
4 1 6 2 12 22
注意
考虑第二个例子。
如果$$$n=1$$$,建造实验室的唯一方法就是放置一个方块。在这种情况下,周长将等于四。
当$$$n=2$$$时,您必须并排放置两个方块。这可以垂直或水平完成,因此有两种方法。在本例中,很容易看出实验室有六面外墙。
对于$$$n=7$$$,所有$$$22$$$最优方案如下图所示。