Feynman Decorando Números

Richard Feynman foi o primeiro a propor a utilização de um fenômeno quântico para executar rotinas computacionais. Foi numa palestra apresentada na Primeira Conferência de Computação Física no MIT. Ele mostrou que um computador clássico levaria muito tempo para simular um simples experimento de física quântica. Reza a lenda que ele conseguia memorizar grandes sequências de números e calcular mentalmente várias propriedades a uma velocidade super-rápida.

Os caçadores de mitos, ao saber disso, resolveram verificar essa lenda diretamente com Feynman usando a sua máquina do tempo. Para verificar, eles iriam gerar uma sequência de números e perguntar de quantas formas podemos escolher exatamente 4 elementos dessa sequência que somem $X$. E a criação do teste foi designada para você, novo estagiário dos caçadores de mitos.

Sua tarefa é escrever um programa que, dado um conjunto de números e múltiplos valores de consulta, determine quantas quádruplas ${i, j, k, l}$ com $1 ≤ i < j < k < l ≤ N$ possuem soma $A_i + A_j + A_k + A_l$ igual aos valores consultados.

A entrada consiste em um único caso de teste. A primeira linha contém um inteiro $N$ $(4 ≤ N ≤1000)$, representando a quantidade de números da sequência. A segunda linha contém $N$ inteiros $a_i$ $(0 ≤ |a_i | ≤ 1000)$, separados por espaço. A terceira linha contém um inteiro $Q$ $(1 ≤ Q ≤ 4000)$, representando o número de consultas. Por fim, cada uma das próximas $Q$ linhas contém um inteiro $q_i$ $(0 ≤ |q_i | ≤ 4000)$ cada, representando os valores-alvo consultados.

Para cada consulta, seu programa deve imprimir uma linha contendo um único inteiro: a quantidade de quádruplas cuja soma é igual a $q_i$ .