Jogo do Poder

Jonathan está empolgado com a nova sensação do momento: o Jogo do Poder. Este jogo é jogado em uma matriz de $N$ linhas e $M$ colunas, na qual cada célula possui um monstro. O monstro na linha $i$ e coluna $j$ possui poder $P_{i,j}$.

No início do jogo, Jonathan escolhe um dos $N \times M$ monstros para jogar. O monstro escolhido por Jonathan se torna o herói do jogo e começa o jogo com o poder indicado em sua célula. Jonathan pode mover o herói ortogonalmente (isto é, para cima, baixo, direita ou esquerda) na matriz enquanto o herói estiver vivo. O herói não pode sair da matriz, mas pode visitar a mesma célula múltiplas vezes.

Toda vez que o herói entra em uma célula com um monstro vivo, ocorre uma batalha entre o herói e o monstro da célula. O herói ganha a batalha se, e somente se, o seu poder for maior ou igual ao poder do monstro. Caso contrário, o herói morre e perde o jogo em game over. Toda vez que o herói ganha uma batalha, o monstro derrotado morre (ou seja, a célula não possui mais nenhum monstro) e, como recompensa, o poder do monstro é somado ao poder do herói (ou seja, se o herói matar o monstro da célula $(i, j)$, o poder do herói aumenta em $P_{i,j}$).

Jonathan percebeu que o jogo pode ser injusto: mesmo que ele jogue de maneira ótima, dependendo de sua escolha de herói, pode ser possível matar todos os monstros, apenas alguns ou até mesmo nenhum monstro.

Decidido a “platinar” o jogo, Jonathan precisa saber o poder máximo que cada herói consegue alcançar (ou seja, o poder máximo possível de ser atingido ao iniciar o jogo em cada célula da matriz) se o jogo for jogado de forma ótima. Felizmente, ele descobriu que os alunos da OBI (Organização dos Bons Informáticos) recentemente resolveram o Jogo da Vida, seu terceiro jogo favorito (atrás do Jogo do Poder e do Jogo de Corrida, claro), então ele pediu a sua ajuda novamente! Determine, para cada herói, o poder máximo que ele consegue alcançar caso Jonathan jogue de forma ótima.

Entrada

A primeira linha de entrada contém dois inteiros $N$ e $M$, o número de linhas e o número de colunas da matriz, respectivamente.

As próximas $N$ linhas contém M inteiros cada. O $j$-ésimo inteiro da $i$-ésima linha contém o poder $P_{i,j}$ do monstro na $i$-ésima linha e $j$-ésima coluna.

Saída

O seu programa deverá imprimir $N$ linhas, cada uma contendo $M$ inteiros. O $j$-ésimo inteiro da $i$-ésima linha deve ser o poder máximo que Jonathan consegue alcançar caso ele escolha como herói o monstro da célula $(i, j)$ e jogue de maneira ótima.

Restrições

• $1 \leq N \leq 100\ 000$
• $1 \leq M \leq 100\ 000$
• $1 \leq N × M \leq 100\ 000$
• $1 \leq P_{i,j} \leq 1\ 000\ 000\ 000$ para todo $1 \leq i \leq N$ e $1 \leq j \leq M$

Atenção: Observe que não é possível declarar $100\ 000 \times 100\ 000$ inteiros (com matriz, vetor etc.) sem estourar o limite de memória (isto causaria erros no programa pois tentaria usar dezenas de GB de memória). Preste atenção ao limite $N \times M \leq 100\ 000$, que garante que a matriz sempre terá no máximo $100\ 000$ células.

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
• Subtarefa 2 (11 pontos):
  • $N =1$
  • $M \leq 1\ 000$
  • $1 \leq P_{1,j} \leq 2$ para todo $1 \leq j \leq M$
• Subtarefa 3 (13 pontos):
  • $N =1$
  • $M \leq 1\ 000$
• Subtarefa 4 (29 pontos):
  • $N = 1$
• Subtarefa 5 (17 pontos):
  • $N \leq 30$
  • $M \leq 30$
• Subtarefa 6 (30 pontos): Sem restrições adicionais.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

2 3
2 3 9
1 7 200

Exemplo de saída 1

6 6 22
1 22 222

Exemplo de entrada 2

1 7
6 3 10 1 20 7 7

Exemplo de saída 2

9 3 54 1 54 14 14

Exemplo de entrada 3

5 6
10 10 10 10 10 10
10 10 1 1 1 10
10 10 10 1 10 10
10 10 10 4 10 10
10 10 10 10 10 2

Exemplo de saída 3

250 250 250 250 250 250
250 250 8 8 8 250
250 250 250 8 250 250
250 250 250 8 250 250
250 250 250 250 250 2