SPOJ Brasil

Kiko ganhou de sua mãe um presente, o Jogo dos Números. O jogo veio em uma caixa, e dentro da caixa há algumas peças de madeira com um número escrito (não há números repetidos). Ele deve ser jogado por duas pessoas, por isto ele chamou seu melhor amigo, o Chaves. As regras são simples, cada um escolhe alguns números dentro da caixa (no mínimo 1 peça). É óbvio que eles devem escolher peças distintas. O objetivo do jogo é que a soma dos números escolhidos por cada um seja a mesma, por isto ou os dois ganham ou os dois perdem, é um jogo cooperativo!

Eles jogaram por várias horas e não conseguiram ganhar. Por isso, estão suspeitando de que o jogo está com defeito. Sua tarefa aqui é, dado os números, responder se é possível que exista uma combinação onde os dois ganham!

Entrada

Há múltiplos casos de teste. Cada caso de teste é dado em duas linhas. A primeira linha contém um inteiro N, que é o número de peças do jogo (2 ≤ N ≤ 1000). A segunda linha contém N inteiros a₁, a₂, ..., a_N, que são números escritos em cada uma das N peças. Você pode supor que 1 ≤ a_i ≤ 10⁶ para todo i, e que se i != j então a_i != a_j (i.e., não existem peças repetidas).

A entrada termina quando N=0.

Saída

Para cada caso de teste, imprima uma linha contendo o caractere S se existir uma combinação que permita que Kiko e Chaves ganhem o jogo, ou o caractere N caso contrário.

Exemplos

Entrada:
3
1 2 3
3
1 2 4
6
1 3 5 7 9 13
10
513 8612 4359 7784 7470 8399 1776 4471 8879 6302
10
5024 579 6948 645 292 8522 9293 4463 976 4089
10
6400 4160 2309 3175 1483 5261 7886 86 9433 4985
10
8193 8898 1380 485 9287 2057 3271 6226 7060 5727
0

Saída:
S
N
S
N
S
N
N