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 \leq N \leq 500$ e $1 \leq M \leq 500$.
• Cada elemento da matriz está entre $0$ e $10^5$.

Informações sobre a pontuação

• Em um conjunto de casos de teste equivalente a $80$ pontos, $N \leq 50$ e $M \leq 50$.

Exemplos

Exemplo de entrada 1

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

Exemplo de saída 1

S

Exemplo de entrada 2

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

Exemplo de saída 2

S

Exemplo de entrada 3

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

Exemplo de saída 3

N