1023 : Count Different Numbers II

Description

Given a series of n numbers and q queries width w, find the total number of different numbers of all consecutive w numbers for each query.

For example: the numbers are {2, 2, 1, 3, 4, 4, 5} and w is 3. All the consecutive w numbers are:

{2, 2, 1}, 2 different numbers 2 and 1;
{2, 1, 3}, 3 different numbers 2, 1 and 3;
{1, 3, 4}, 3 different numbers …
{3, 4, 4}, 2 different numbers …
{4, 4, 5}, 2 different numbers …

The answer is 2 + 3 + 3 + 2 + 2 == 12.

Input

There are no more than 20 test cases. Each case contains three lines.

The first line has two integer numbers n and q.

The second line are n integer numbers.

1 <= n <= 10^4 and all the n integer numbers are in range [1, 10^4].

The third line are q integer numbers denote each w.

1 <= q <= 10^4, 1 <= w <= n.

Output

For each case, output q lines, the answer for each query.

Sample

7 3
2 2 1 3 4 4 5
2 3 7

10
12
5

Hint

Source

Author

Reference: 2012 Asia Hangzhou Regional Contest - C