Sums of Triplets

Yet another popular exercise from job interviews: In array of numbers find a pair of elements which produces the requested sum.
Important point is that we are expected to provide some better solution than naive nested loop like this (for this is O(n^2) in time):

for a in array:
    for b in array:
        if sum = a+b:
            print a, b

This problem is just a bit harder. Let us search for triples of numbers instead of pairs.

Input data have several parts:

• first line contains N and K where the first is the size of array (below 1000) and the second is explained below
• next line contains K values - list of sums we search for (sorted)
• next lines (up to 100) contain N values of array, they are sorted and have no duplicates

Output data should contain K values, telling how many ways there are to construct respective sum using some 3 elements of array.

Example (simplified):

input data:
15 3
60 100 1000
10 20 30 40 50 60 70 80 90 100
200 300 400 500 600

answer:
1 4 3