Mancha

Juninho está participando de um projeto de iniciação científica sobre identificação de doenças de pele através de análises de imagens digitais. Muitas vezes o formato de uma lesão de pele, ou mancha, pode indicar as possibilidades de diagnóstico. O professor orientador tem algumas imagens digitalizadas de manchas e precisa identificar aquelas que são "regulares" segundo uma definição bastante precisa, que será dada abaixo. Juninho precisa da sua ajuda para processar a imagem da mancha e decidir se ela é ou não regular.

A imagem é um reticulado de N x N pixels. Os pixels escuros representam a mancha, que é sempre conexa, ou seja, é composta de apenas uma componente. De forma mais precisa, dado qualquer par de pixels pertencentes à mancha, sempre existe um caminho, uma sequência de pixels escuros entre eles seguindo somente por direções ortogonais, totalmente contido dentro da mancha. A figura acima ilustra três possíveis manchas, para N=10.

Dados dois pixels P e Q, a distância de Manhattan entre eles é definida como: d_manhattan(P,Q)=|P_l-Q_l|+|P_c-Q_c|, onde P_l é o índice da linha do pixel P e P_c é o índice da coluna do pixel P, na imagem digitalizada. O mesmo vale para Q_l e Q_c. Ou seja, a distância de Manhattan é a soma da diferença absoluta entre a linha de P e a linha de Q com a diferença absoluta entre as colunas de P e Q. Dados dois pixels P e Q que pertencem à mancha, definiremos d(P,Q> como sendo o comprimento do menor caminho existente entre P e Q, que esteja totalmente contido dentro da mancha.

No exemplo da figura mais à esquerda, onde P e Q estão representados por um pequeno círculo, d(P,Q>=9 e d_manhattan(P,Q)=9. Na figura do meio, d(P,Q>=10 e d_manhattan(P,Q)=6; e na figura mais à direita, d(P,Q>=5 e d_manhattan(P,Q)=3.

Finalmente, uma mancha será regular se, para qualquer par de pixels P e Q pertencentes à mancha, tivermos d(P,Q>=d_manhattan(P,Q). Dessa forma, verifique que a figura mais à esquerda ilustra uma mancha regular, enquanto que as outras duas são irregulares.

Entrada

A primeira linha da entrada contém um inteiro N, representando as dimensões da imagem. As N linhas seguintes contêm, cada uma, uma cadeia de N caracteres definindo uma linha de pixels da imagem. Os caracteres podem ser: "." para pixels fora da mancha; e "*" para pixels que pertencem à mancha.

Saída

Imprima uma linha contendo o caractere "S", se a mancha for regular; ou "N", se for irregular.

Restrições

• 2 ≤ N ≤ 1000;
• A mancha possui pelo menos dois pixels.

Informações sobre a pontuação

• Para um conjunto de casos de teste valendo 20 pontos, N ≤ 20;
• Para um conjunto de casos de teste valendo 40 pontos, N ≤ 100.

Exemplos

10
..........
.....*....
...***....
..*****...
..*****...
..*******.
.********.
...*****..
......**..
..........

S
	

10
..........
....*.***.
....*.***.
..******..
..****....
....**....
....****..
...*****..
.......*..
..........

N
	

2
.*
**

S