Laboratory on Pluto
Contest: Codeforces Round 843 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, dp, greedy, math

As you know, Martian scientists are actively engaged in space research. One of the highest priorities is Pluto. In order to study this planet in more detail, it was decided to build a laboratory on Pluto.

It is known that the lab will be built of $$$n$$$ square blocks of equal size. For convenience, we will assume that Pluto's surface is a plane divided by vertical and horizontal lines into unit squares. Each square is either occupied by a lab block or not, and only $$$n$$$ squares are occupied.

Since each block is square, it has four walls. If a wall is adjacent to another block, it is considered inside, otherwise — outside.

Pluto is famous for its extremely cold temperatures, so the outside walls of the lab must be insulated. One unit of insulation per exterior wall would be required. Thus, the greater the total length of the outside walls of the lab (i. e., its perimeter), the more insulation will be needed.

Consider the lab layout in the figure below. It shows that the lab consists of $$$n = 33$$$ blocks, and all the blocks have a total of $$$24$$$ outside walls, i. e. $$$24$$$ units of insulation will be needed.

You should build the lab optimally, i. e., minimize the amount of insulation. On the other hand, there may be many optimal options, so scientists may be interested in the number of ways to build the lab using the minimum amount of insulation, modulo a prime number $$$m$$$.

Two ways are considered the same if they are the same when overlapping without turning. Thus, if a lab plan is rotated by $$$90^{\circ}$$$, such a new plan can be considered a separate way.

To help scientists explore Pluto, you need to write a program that solves these difficult problems.

Input format:
The first line contains two integers $$$t$$$ and $$$u$$$ ($$$1 \le t \le 2\cdot 10^5$$$, $$$1 \le u \le 2$$$) — the number of test cases and the test type. If $$$u=1$$$, you need to find any way to build the lab in an optimal way, and if $$$u=2$$$, you need to calculate the number of ways to do it.

If $$$u=2$$$, then in the following line of input there is a prime integer $$$m$$$ ($$$10^8 \le m \le 10^9 + 9$$$), modulo which you need to calculate the number of ways.

Each of the following $$$t$$$ lines of input contains a description of a test case consisting of one integer $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — the number of blocks the lab should consist of.

It is guaranteed that if $$$u=1$$$, then the sum of $$$n$$$ on all test cases does not exceed $$$8\cdot10^5$$$.

Output format:
For each test case, output the answers in the format below, separating them with a newline. The output format depends on $$$u$$$ in the input data.

If $$$u=1$$$, in the first line you need to print two integers $$$h$$$ and $$$w$$$ —the height and width of the area in which the lab should be built. Then, in each of the following $$$h$$$ lines, you must output a line $$$s_i$$$ consisting of $$$w$$$ characters "#" and ".". If the $$$j$$$-th character of the row $$$s_i$$$ is "#", then the corresponding square must contain a block of laboratory, otherwise, it is considered empty. Thus, we get a matrix of symbols. The condition must also be met that the first and last rows of the matrix, as well as the first and last columns, must have at least one character "#", otherwise we could output the same lab layout, but with smaller $$$h$$$ and $$$w$$$. If there are many options to build an optimal lab, you can print any of them.

If $$$u=2$$$, you need to print two integers $$$p$$$ and $$$c$$$ — the number of outside walls in an optimal lab, and the remainder of the number of ways by prime modulo $$$m$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the second example.

If $$$n=1$$$, the only way to build a lab is to place a single block. In this case, the perimeter will be equal to four.

When $$$n=2$$$, you must place two blocks side by side. This can be done either vertically or horizontally, so there are two ways. It is easy to see that the lab has six outside walls in this case.

For $$$n=7$$$, all the $$$22$$$ optimal plans are shown in the picture below.

Example input:
3 1
1
2
7

Example output:
1 1
#
1 2
##
2 4
.###
####

Example input:
3 2
1000000007
1
2
7

Example output:
4 1
6 2
12 22

Editorial:
Let us find out the minimal perimeter for a fixed $$$n$$$ in $$$O(1)$$$.
Let $$$a = \lfloor \sqrt{n} \rfloor$$$:
1. If $$$a^2 < n$$$ and $$$n \leq a \cdot (a+1)$$$, then the minimum perimeter will be $$$2 \cdot (2 \cdot a + 1)$$$.
2. If $$$a \cdot a + a < n$$$ and $$$n \leq (a + 1)^2$$$, then the minimum perimeter will be $$$4 \cdot (a + 1)$$$.
3. If 1) and 2) are not satisfied, then the minimum perimeter is $$$4 \cdot a$$$.
For convenience, we denote the semiperimeter by $$$p$$$. Let's check one of the rectangle's side $$$x$$$ from $$$1$$$ to $$$p$$$. We will immediately get $$$y = p - x$$$. Then if the area of the rectangle is at least $$$n$$$, then for tests with $$$u=1$$$ we can derive a rectangle with sides $$$x$$$ and $$$y$$$ by removing some number of cells from the 1st row or column of this matrix.
Consider a matrix with sides $$$x$$$ and $$$y$$$ with minimal perimeter and area at least $$$n$$$. It is easy to see that if we gradually remove one corner cell of a given figure, the perimeter will not change. Suppose we have some good figure. Let's look at all four figures that form empty cells in the matrix. These figures form a kind of 'staircase', that is, the number of cells in the past row is not less than the number of cells. Why is this so? Suppose that in some line we delete a cell so that the figure ceases to form a staircase. In that case the perimeter of the piece will increase by $$$2$$$, which will be the bad piece.
Now the problem is reduced to the following:
For each matrix with dimensions $$$x$$$ by $$$y$$$ with minimal perimeter and area not less than $$$n$$$, calculate the number of ways to arrange the staircases in 4 corners such that the sum of cells occupied by the staircases equals $$$x \cdot y - n$$$. How to do this?
Assume DP $$$dp_{angles, sum, last}$$$ — the number of ways to arrange staircases in $$$angles$$$, not more than 4, so that the sum of all cells occupied by staircases equals $$$sum$$$ and the length of the last line of staircase equals $$$last$$$. Then how to count the given DP? Go through $$$angles, sum, last$$$ and $$$cur \leq last$$$ - the length of the line we will add to the current staircase, then go from $$$dp_{angles, sum, last}$$$ to $$$dp_{angles, sum + cur, cur}$$$. Or go to the next corner $$$dp_{angles + 1, sum, maxP}$$$. This DP works for $$$O(n \cdot \sqrt{n})$$$.
To answer $$$n$$$ we go through all good rectangles, as specified above, and add $$$f_{4, x \cdot y - n, maxP}$$$ to the answer.
To solve the problem for a full score, you must optimize the above DP to $$$O(n)$$$. The final difficulty is $$$O(n + t \cdot \sqrt{n})$$$.