冥王星实验室

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

在无限单位方格平面上放置恰好 $n$ 个正方形模块。一个模块的某条边若不与另一个模块相邻，就是实验室的一段外墙。实验室周长定义为所有外墙的总长度。

你需要使周长最小。输入给出两种任务类型：

• 当 $u=1$ 时，输出任意一种周长最小的布局；
• 当 $u=2$ 时，输出最小周长，以及达到该周长的不同布局数量对质数 $m$ 取模的结果。

两个布局经过平移后完全重合才视为相同；不允许通过旋转或翻转判为相同。因此，一个布局旋转 $90^\circ$ 后通常是另一个布局。

本题使用特殊判题。对 $u=1$，判题器会直接验证模块数、最小外接矩形和周长；你不必与标准输出相同。

输入格式

第一行两个整数 $t,u$，分别表示测试组数和任务类型。

若 $u=2$，第二行包含一个质数 $m$，表示计数答案所用的模数。

接下来 $t$ 行，每行一个整数 $n$。

输出格式

对每组测试分别输出答案。

若 $u=1$，先输出两个整数 $h,w$。随后输出 $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

数据范围

对所有数据，$1\le t\le2\times10^5$，$u\in\{1,2\}$，$1\le n\le4\times10^5$。当 $u=2$ 时，$m$ 是质数且 $10^8\le m\le10^9+9$。当 $u=1$ 时，同一输入文件内所有 $n$ 之和不超过 $8\times10^5$。

每个测试点独立计分。