SPOJ Brasil

Quando limpavam o porão da casa recentemente herdada, os primos João e José descobriram um antigo mapa guardado no baú que havia sido de seu bisavô. O mapa parecia descrever uma ilha, era muito antigo, e em meio a indicações de caminhos pela ilha, continha apenas um nome: Huyn Chong Chong. Curiosos, João e José pesquisaram o nome na bilbioteca do colégio e na Internet. Para sua surpresa e excitação, o nome era relacionado a uma antiga lenda de um tesouro escondido por piratas no século XVIII.

Encantados com a lenda, os primos acreditaram ter encontrado o mapa que os levaria ao tesouro, escondido na ilha de Huyn Chong Chong, próximo à Coréia do Sul. O tesouro, dizia a lenda, continha uma arca cheia de pedras preciosas muito raras e valiosas. Certos de que encontrariam o tesouro, os primos embarcaram rumo à ilha. Cada um dos primos se imaginava mais esperto do que o outro, e acreditava que encontraria o tesouro primeiro. Assim, eles combinaram que cada um ficaria com a parte do tesouro que encontrasse. Os primos então se separaram, e começaram a procurar o tesouro, especialmente a arca. Cada um dos primos tomou o caminho que imaginava que o levaria até a arca, e seguindo a indicação do mapa, ambos foram encontrando várias jóias pelo caminho. Coincidentemente, os dois primos cheragam ao mesmo tempo no local onde a arca estava escondida. Como os dois encontraram a arca ao mesmo tempo, eles tinham agora que decidir como dividir o tesouro. Depois de analisar algumas alternativas, os primos concordaram em fazer a divisão da seguinte forma. Cada um ficaria com a parte do tesouro que encontrou antes de chegar à arca, e o conteúdo da arca seria dividido de forma que os dois ficassem com partes do tesouro total de mesmo valor. Para fazer a divisão desta forma, ao chegar de volta ao Brasil, os primos mandaram avaliar cada jóia do tesouro. Contudo, eles estão agora em dúvida se é possível fazer a divisão conforme eles haviam combinado. Você, como amigo dos dois primos (agora milionários), e esperando receber alguma recompensa, dispôs-se a ajudá-los a descobrir se é possível fazer tal divisão.

Tarefa

São dados:

• o valor dos objetos coletados por João e por José antes de encontrarem a arca;
• uma lista de valores, correspondentes aos objetos encontrados dentro da arca.

Como as jóias são muito valiosas, estes valores são dados em unidades de R$ 1.000,00, ou seja, o valor 10 significa R$ 10.000,00. Você deve escrever um programa que determina se é possível dividir os objetos da arca de forma que, considerados também os valores dos objetos encontrados anteriormente (que ficarão com quem os encontrou), os primos recebam partes do tesouro com o mesmo valor.

Entrada

Seu programa deve ler vários conjuntos de testes. A primeira linha de um conjunto de testes contém três números inteiros X, Y e N. Os valores X eY representam respectivamente a soma dos valores encontrados por João e por José antes de chegarem à arca. O valor N indica o número de objetos encontrados na arca. Seguem-se N linhas, cada uma contendo um número inteiro V, correspondendo ao valor de um dos objetos da arca. O final da entrada é indicado por X = Y = N = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter o caractere ‘S’ caso seja possível dividir o tesouro como combinado pelos dois primos, ou o caractere ‘N’ caso contrário. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
10 20 4
3
8
7
2
1 1 6
2
7
7
12
5
3
0 0 0

Saída:
Teste 1
S

Teste 2
N

Restrições

0 <= X <= 50 (X = 0 apenas para indicar o final da entrada)
0 <= Y <= 50 (Y = 0 apenas para indicar o final da entrada)
0 <= N <= 100 (N = 0 apenas para indicar o final da entrada)
1 <= V <= 100