URI Online Judge | 2450

Matrix Ladder

By OBI - Olimpíada Brasileira de Informática 2014 BR Brazil

Timelimit: 1

Joaozinho is learning about arrays. Today he learned how to make arrays on the ladder shape, and exercising. To help him, you should write a program that determines if the result of it really is in the correct format.

A matrix is ladder shaped when, for each line, the following conditions are met:

Input

The first line has two integers N and M (1 ≤ N, M ≤ 500), the dimensions of the matrix. Each of the following N lines contains M (0 ≤ Mij ≤ 105) non-negative integers, the array elements.

Output

Your program should produce a single line containing the character 'S' if the array is in ladder format, or 'N' otherwise.

Input Samples Output Samples

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

S

5 8

0 5 1 0 3 2 2 0

0 0 0 0 4 0 1 2

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

S

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

N