| Codeforces Round 843 (Div. 2) |
|---|
| Закончено |
Как известно, марсианские ученые активно занимаются космическими исследованиями. Одно из самых приоритетных направлений — Плутон. Чтобы изучить эту планету более детально, было решено построить на Плутоне лабораторию.
Известно, что лаборатория будет построена из $$$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$$$), по модулю которого необходимо вычислять количество способов.
В каждой из следующих $$$t$$$ строк входных данных находится описание тестового примера, состоящее из одного целого числа $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — количество блоков, из которых должна состоять лаборатория.
Гарантируется, что если $$$u=1$$$, то сумма $$$n$$$ по всем тестовым примерам не превосходит $$$8\cdot10^5$$$.
Для каждого тестового примера необходимо вывести ответы в формате ниже, разделяя их переводом строки. Формат выходных данных при этом зависит от $$$u$$$ во входных данных.
Если $$$u=1$$$, то необходимо в первой строке вывести через пробел два целых числа $$$h$$$ и $$$w$$$ — высота и ширина участка, на котором должна быть построена лаборатория. Далее, в каждой из следующих $$$h$$$ строк необходимо вывести строки $$$s_i$$$, состоящие из $$$w$$$ символов «#» и «.» каждая. Если $$$j$$$-й символ строки $$$s_i$$$ равен «#», то тогда на соответствующем квадрате должен располагаться блок лаборатории, иначе он считается пустым. Таким образом, мы получаем матрицу из символов. Должно также выполняться условие, что в первой и последней строках матрицы, а также в первом и последнем столбцах, должен быть хотя бы один символ «#», иначе можно было бы вывести такой же план лаборатории, но с меньшими $$$h$$$ и $$$w$$$. Если вариантов построить оптимальную лабораторию несколько, выведите любой из них.
Если $$$u=2$$$, то необходимо вывести через пробел два целых числа $$$p$$$ и $$$c$$$ — количество внешних стен в оптимальной лаборатории, а также остаток от деления количества способов на $$$m$$$.
3 1127
1 1 # 1 2 ## 2 4 .### ####
3 21000000007127
4 1 6 2 12 22
Рассмотрим второй пример.
При $$$n=1$$$ единственный способ построить лабораторию — разместить единственный блок. При этом периметр будет равен четырем.
При $$$n=2$$$ необходимо разместить два блока рядом. Это можно сделать как по вертикали, так и по горизонтали, поэтому есть два способа. Нетрудно убедиться, что в данном случае у лаборатории шесть внешних стен.
При $$$n=7$$$ все $$$22$$$ оптимальных плана показаны на рисунке ниже:
