Продажа земли
Как вы, возможно, знаете, страна Абсурдистан полна аномалий. Например, всю страну можно разделить на единичные квадраты, которые либо травяные, либо болотистые. Также страна известна своими неспособными бюрократами. Если вы хотите купить участок земли (называемый парцеллой), вы можете купить только прямоугольную область, потому что они не могут справиться с другими формами. Цена парцеллы определяется ими и пропорциональна периметру парцеллы, так как бюрократы не могут умножать целые числа и, следовательно, не могут вычислить площадь парцеллы.
Пер владеет парцеллой в Абсурдистане, окруженной болотом, и хочет продать её, возможно, частями, некоторым покупателям. Когда он продает прямоугольную часть своей земли, он обязан сообщить об этом местным бюрократам. Сначала они скажут ему цену, по которой он должен её продать. Затем они запишут имя нового владельца и координаты юго-восточного угла продаваемой парцеллы. Если кто-то уже владеет парцеллой с юго-восточным углом в том же месте, бюрократы откажут в изменении права собственности.
Пер понимает, что он может легко обмануть систему. Он может продавать пересекающиеся области, потому что бюрократы проверяют только идентичность юго-восточных углов. Однако никто не хочет покупать парцеллу, содержащую болото.
В этом примере темные квадраты представляют болото. Пер может, например, продать три пересекающиеся серые области размером 2 × 1, 2 × 4 и 4 × 1 соответственно. Общий периметр составляет 6 + 12 + 10 = 28.
Заметьте, что он может получить больше денег, продавая ещё больше земли. Эта фигура соответствует случаю в примере ввода.
Теперь Пер хотел бы знать, сколько парцелл каждого периметра ему нужно продать, чтобы максимизировать свою прибыль. Можете ли вы ему помочь? Вы можете предположить, что он всегда сможет найти покупателя для каждого участка земли, если он не содержит болот. Также Пер уверен, что ни один квадрат в его парцелле не принадлежит кому-то другому.
Входные данные
На первой строке положительное целое число: количество тестов, не более 100. После этого для каждого теста:
Одна строка с двумя целыми числами n и m (1 ≤ n, m ≤ 1 000): размеры парцеллы Пера.
n строк, каждая с m символами. Каждый символ либо '#', либо '.'. j-й символ в i-й строке — это '#', если позиция (i, j) является болотом, и '.', если это трава. Северо-западный угол парцеллы Пера имеет координаты (1, 1), а юго-восточный угол имеет координаты (n, m).
Выходные данные
Для каждого теста:
Ноль или более строк, содержащих полный список того, сколько парцелл каждого периметра Пер должен продать, чтобы максимизировать свою прибыль. Более конкретно, если Пер должен продать pi парцелл с периметром i в оптимальном решении, выведите одну строку "p_i × i". Строки должны быть отсортированы в порядке возрастания i. Не должно быть двух строк с одинаковым значением i, и вы не должны выводить строки с p_i = 0.