Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ESCADA14 - Matriz Escada

Joãozinho está aprendendo sobre matrizes. Hoje ele aprendeu como deixar matrizes na forma escada, e está exercitando. Para ajudá-lo, você deve escrever um programa que determine se o resultado dele realmente está no formato correto.

Uma matriz está na forma escada quando, para cada linha, as condições a seguir forem satisfeitas:

• Se a linha só possuir zeros, então todas as linhas abaixo desta também só possuem zeros.
• Caso contrário, seja X o elemento diferente de zero mais à esquerda da linha; então, para todas as linhas abaixo da linha de X, todos os elementos nas colunas à esquerda de X e na coluna de X são iguais a zero.

Entrada
A primeira linha possui dois inteiros N e M , as dimensões da matriz. Cada uma das N linhas seguintes contém M inteiros não-negativos, os elementos da matriz.

Saída
Seu programa deve produzir uma única linha, contendo o caractere ‘S’ caso a matriz esteja no formato escada, ou ‘N’, caso contrário.

Restrições
• 1 ≤ N ≤ 500 e 1 ≤ M ≤ 500.
• Cada elemento da matriz está entre 0 e 105.

Exemplos

Entrada
4 6
1 2 9 9 9 9
0 0 3 9 9 9
0 0 0 0 5 9
0 0 0 0 0 6

Saída
S

Entrada
5 8
0 5 1 0 3 2 2 0
0 0 0 0 4 0 1 2
0 0 0 0 0 0 3 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Saída
S

Entrada
5 5
1 1 2 3 4
0 1 1 4 5
0 1 2 3 6
0 0 0 2 0
0 0 0 0 0

Saída
N


Adicionado por:Edmundo Rodrigues
Data:2014-05-30
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 ASM32 GAWK BASH BF C CSHARP CPP C++ 4.3.2 C99 CLPS LISP clisp LISP sbcl D FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCM guile SCM qobi SED ST WHITESPACE
Origem:Olimpíada Brasileira de Informática 2014 - Nível 2 - Fase 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.