It is currently 1 AM, and NK is writing problems for an upcoming CBOJ contest.

NK was writing the fifth problem of his contest when he fell asleep. While sleeping, NK dreamed of solving a CBOJ problem.

Given an integer \(N\) and an array \(A\) of length \(N\), answer \(Q\) queries where you are given an integer \(x\), and you have to output the number of triples, \((i, j, k)\), such that \(A_i^x + A_j^x = A_k^x\)

When NK woke up, he attempted to solve the problem, but just could not figure it out. So, NK decided to ask Jeff_Ray.

Of course, Jeff_Ray solved the problem immediately, but left the solution of the problem as an exerise for the reader.

Please help NK solve the problem.

Constraints

\(1 \le N \le 1000\)

\(1 \le Q \le 1000\)

\(1 \le A_i \le 10^9\)

\(1 \le x_i \le 100\)

Input Specification

The first line contains two integers \(N\) and \(Q\), the length of the array and the number of queries respectively.

The next line contains \(N\) space-separated integers, \(A_i\), the elements of the array.

The next \(Q\) lines each contain an integer, \(x_i\), the exponent used in the query.

Output Specification

Output \(Q\) lines, on the \(i\)-th line output the answer to \(i\)-th query.

Sample Input

5 2
5 3 1 4 5
1
2

Sample Output

6
4

Note: The indices \((i, j, k)\) do not have to be unique.