XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: pastas.x, onde x deve ser c, cpp, java, js ou py

Pastas

Estela é uma secretária dedicada da OBI (Organização Burocrática Internacional), um megaconglomerado empresarial voltado a criação de documentos e preenchimento de formulários. Todo dia ela recebe milhares de pastas suspensas e seu objetivo é organizá-las de uma forma que seja simples recuperar uma pasta do arquivo.

Cada pasta possui uma pequena aba, que fica anexada à pasta e é visível quando a pasta está suspensa em seu arquivo. Todo funcionário fixa a aba em uma das posições especificadas pelo manual de fixação de abas, embora ele possa escolher, ao acaso, qualquer uma das posições descritas no manual. Tais posições são numeradas de 1 até P .

Estela notou que fica consideravelmente mais fácil encontrar as pastas se elas forem arquivadas da seguinte forma: primeiro uma pasta com aba na posição 1, depois uma com aba na posição 2, e assim sucessivamente, até que uma pasta com aba na posição P seja arquivada. Logo após, repete-se o processo, arquivando uma pasta com aba na posição 1. Para Estela, um conjunto de pastas é arquivado de forma perfeita se todas as pastas desse conjunto forem arquivadas da forma descrita anteriormente, ou seja:

  • Imediatamente após toda pasta com aba na posição I , I < P , existe uma pasta com aba na posição I + 1 ou não há nenhuma pasta.
  • Imediatamente após toda pasta com aba na posição P , existe uma pasta com aba na posição 1 ou não há nenhuma pasta.
  • Todas as pastas do conjunto são armazenadas.

Tarefa

Dado um conjunto de pastas e a posição de suas abas, determinar se é possível arquivar esse conjunto de pastas de forma perfeita.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém dois inteiros P e N que indicam, respectivamente, o número de posições possíveis para se colar as abas (1 ≤ P ≤ 1.000) o número pastas a serem armazenadas (1 ≤ N ≤ 1.000.000). As N linhas seguintes contém um inteiro I (1 ≤ IP ) cada representando a posição onde a aba da I -ésima pasta foi colada.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo a letra S se for possível fazer um arquivamento perfeito ou N caso contrário

Exemplos

Entrada
2 2
1
2
			
Saída
S
			
Entrada
3 6
1
2
3
1
2
1
			
Saída
N
			
Entrada
4 7
1
1
2
2
3
3
4
			
Saída
S
			
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação