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.
Informações sobre a pontuação
- Em um conjunto de casos de teste equivalente a 80 pontos, N ≤ 50 e M ≤ 50.
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
|
