408318: GYM103092 D Dance

Студенты Suleyman Demirel University ведут очень активный образ жизни. У нас в университете активно действуют более $$$20$$$ разных клубов. Абу, наш главный герой, на сей раз решил попробовать себя в MMDANCE Club. Пока что у него это неплохо получается.

Танцпол можно представить сверху как матрицу $$$A$$$ размера $$$n \times m$$$, где каждая клетка матрицы представляет собой отдельный сектор танцпола. В каждом секторе танцпола стоит ровно один танцор, и его высота равна $$$A_{i, j}$$$. В нашем случае можно считать что росты всех студентов — различные целые числа от $$$1$$$ до $$$n \times m$$$.

Поскольку Абу параллельно является одним из главных лиц ACM CLUB, он тут же по привычке решил посчитать некоторое интересное значение крутости для каждого сектора танцпола. Эту крутость он решил определить вот так:

• Обозначим $$$S_{i, j}$$$ как отсортированное множество ростов всех танцоров, которые стоят по направлению левее, правее, выше и ниже танцора в секторе $$$(i, j)$$$. Это множество также содержит рост этого же танцора $$$A_{i, j}$$$. Более формально, $$$S_{i,j}$$$ содержит все числа находящиеся в $$$i$$$-й строке или $$$j$$$-м столбце матрицы $$$A$$$. У всех этих множеств одинаковая длина — $$$n+m-1$$$.
• Возьмём все эти множества $$$S_{i,j}$$$, запишем их всех в один список $$$T$$$ и отсортируем их лексикографически по возрастанию.
• Крутостью сектора $$$(i,j)$$$ будем считать порядковый индекс множества $$$S_{i,j}$$$ в списке $$$T$$$.

Пока Вы читали условие, Абу уже рассказал своим друзьям значения крутости всех секторов. А сможете вы?

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — размеры танцпола ($$$2 \le n, m \le 250000$$$, $$$4 \leq n \times m \leq 500000$$$)

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ чисел — росты всех танцоров ($$$1 \leq A_{i, j} \leq n \times m$$$)

В ровно $$$n$$$ строках выведите по $$$m$$$ целых чисел — крутости всех секторов танцпола.

2 3
1 6 4
5 2 3

4 2 3
1 6 5

Все числа входящие в $$$S_{2, 2}$$$

Список $$$T$$$:

1. $$$(1, 2, 3, 5)$$$
2. $$$(1, 2, 4, 6)$$$
3. $$$(1, 3, 4, 6)$$$
4. $$$(1, 4, 5, 6)$$$
5. $$$(2, 3, 4, 5)$$$
6. $$$(2, 3, 5, 6)$$$