Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

JOGOMG14 - Jogo dos Números

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 a1, a2, ..., aN, que são números escritos em cada uma das N peças. Você pode supor que 1 ≤ ai ≤ 106 para todo i, e que se i != j então ai != aj (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

Adicionado por:Wanderley Guimarăes
Data:2014-07-10
Tempo limite:10s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.