B. Прямоугольники
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная сетка$$$^{\text{∗}}$$$ $$$G$$$ размером $$$n \times m$$$.

Определим прямоугольник как кортеж $$$(u,d,l,r)$$$, который удовлетворяет следующим условиям:

  • $$$1 \le \boldsymbol{u \lt d} \le n$$$;
  • $$$1 \le \boldsymbol{l \lt r} \le m$$$;
  • Каждая из ячеек $$$(u,l)$$$, $$$(u,r)$$$, $$$(d,l)$$$, $$$(d,r)$$$ содержит $$$1$$$.

Тогда площадь прямоугольника $$$(u,d,l,r)$$$ определяется как $$$(d-u+1) \cdot (r-l+1)$$$.

Например, рассмотрим следующую бинарную сетку:

$$$$$$\begin{matrix} 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix}$$$$$$

Здесь вы можете увидеть два прямоугольника $$$(1,2,1,3)$$$ и $$$(1,3,3,5)$$$$$$^{\text{†}}$$$, которые имеют площади $$$6$$$ и $$$9$$$ соответственно.

Для каждой ячейки $$$(i,j)$$$ найдите минимальную площадь любого прямоугольника $$$(u,d,l,r)$$$, такого что $$$u \le i \le d$$$ и $$$l \le j \le r$$$.

$$$^{\text{∗}}$$$Бинарная сетка — это сетка, в которой каждая ячейка содержит $$$0$$$ или $$$1$$$. Ячейка в $$$j$$$-м столбце $$$i$$$-й строки обозначается как ячейка $$$(i,j)$$$.

$$$^{\text{†}}$$$Обратите внимание, что это единственные прямоугольники в сетке; например, $$$(1,1,1,5)$$$ не является прямоугольником, так как не удовлетворяет условию $$$u \lt d$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n,m$$$, $$$n\cdot m \le 250\,000$$$).

Каждая из следующих $$$n$$$ строк содержит строку длиной $$$m$$$, обозначающую $$$i$$$-ю строку $$$G$$$ ($$$G_{i,j} \in \{0,1\}$$$).

Гарантируется, что сумма $$$n\cdot m$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

Выходные данные

Для каждого набора входных данных выведите сетку из $$$n$$$ строк и $$$m$$$ столбцов. В $$$j$$$-м столбце $$$i$$$-й строки вы должны вывести:

  • Если существует прямоугольник $$$(u,d,l,r)$$$ такой, что $$$u \le i \le d$$$ и $$$l \le j \le r$$$, выведите минимальную площадь любого такого прямоугольника;
  • В противном случае выведите $$$0$$$ вместо этого.
Пример
Входные данные
3
3 5
10101
10100
00101
4 6
011101
010001
100010
101110
5 5
11100
10110
11111
01101
00111
Выходные данные
6 6 6 9 9
6 6 6 9 9
0 0 9 9 9
0 10 8 8 10 10
0 10 8 8 10 10
10 10 8 8 10 0
10 10 8 8 10 0
6 6 6 0 0
6 6 4 4 0
6 4 4 4 6
0 4 4 6 6
0 0 6 6 6
Примечание

Первый набор входных данных объяснён в условии.

Для третьего набора входных данных существует шесть прямоугольников, которые содержат хотя бы одну ячейку и имеют минимальную площадь:

  • $$$(1,3,1,2)$$$, площадь которого $$$6$$$;
  • $$$(1,2,1,3)$$$, площадь которого $$$6$$$;
  • $$$(3,4,2,3)$$$, площадь которого $$$4$$$;
  • $$$(2,3,3,4)$$$, площадь которого $$$4$$$;
  • $$$(3,5,4,5)$$$, площадь которого $$$6$$$;
  • $$$(4,5,3,5)$$$, площадь которого $$$6$$$.