28a Olimpíada Brasileira de Informática
Submeta sua solução

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 × 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 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 100 000
  • 1 ≤ N × M ≤ 100 000
  • 1 ≤ P_{i,j} ≤ 1 000 000 000 para todo 1 ≤ i ≤ N e 1 ≤ j ≤ M
Atenção: Observe que não é possível declarar 100 000 × 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 × M ≤ 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 ≤ 1000
    • 1 ≤ P_{1,j} ≤ 2 para todo 1 ≤ j ≤ M
  • Subtarefa 3 (13 pontos):
    • N=1
    • M ≤ 1000
  • Subtarefa 4 (29 pontos):
    • N=1
  • Subtarefa 5 (17 pontos):
    • N ≤ 30
    • M ≤ 30
  • Subtarefa 6 (30 pontos): Sem restrições adicionais.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (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 qualquer uma das suas submissões.

Exemplos

Entrada
2 3
2 3 9
1 7 200
Saída
6 6 22
1 22 222
	

 

Entrada
1 7
6 3 10 1 20 7 7
Saída
9 3 54 1 54 14 14
	

 

Entrada
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
Saída
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
	

 

PJ P1 P2 PS
Tarefas Programação Nível Sênior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação