[ED165] Somas

Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 30 de Dezembro
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #11]

[ED165] Somas

Neste problema deverá submeter uma classe ED165 contendo um programa completo para resolver o problema (ou seja, com o método main).
Pode assumir que no Mooshak terá acesso às classes de árvores binárias de pesquisa (ou seja, não precisa de incluir a classe BSTree no código submetido).

O problema

Dada um conjunto de N números e um conjunto de P perguntas indicando cada uma um número X_i, a tua tarefa é descobrir, para cada pergunta, se o número X_i pode ser formado somando dois números (possivelmente iguais) do conjunto dado.

Imagine por exemplo que o conjunto é {2,6,8,10}:

4 (2+2), 8 (2+6), 10 (2+8), 12 (2+10) e 16 (6+10) são exemplos de perguntas que teriam resposta afirmativa
2, 3, 5, 15 ou 21 são exemplos de perguntas que teriam resposta negativa

Input

Na primeira linha do input vem um número N (1 ≤ N ≤ 1,000) que corresponde à quantidade de números do conjunto. Segue-se uma linha com N inteiros positivos (menores que um milhão), separados por um espaço, indicando os números do conjunto.

Na terceira linha do input vem um número P (1 ≤ N ≤ 5,000) que corresponde à quantidade de perguntas. Segue-se uma linha com P inteiros positivos (menores que um milhão), separados por um espaço, indicando as perguntas X_i.

Output

O output deve ser constituído por P linhas, uma por cada pergunta, no formato X_i: sim se o X_i puder ser formado como soma de dois números do conjunto dado, ou X_i: nao caso contrário.

Exemplo de Input

4
10 6 2 8
10
4 8 2 5 21 10 16 3 12 15

Exemplo de Output

4: sim
8: sim
2: nao
5: nao
21: nao
10: sim
16: sim
3: nao
12: sim
15: nao

Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto