CEOI '18 P3 - Lottery

View as PDF

Points: 25 (partial)
Time limit: 1.4s
Memory limit: 32M

Problem types

For a long long time you have been a big fan of Bytelotto. For around the same time, the members of your family have been telling you that all such games are a waste of money. You are sure that it is because of their lack of skill! You have a brilliant plan and everyone will see you winning the game soon.

There are many types of games. You are interested in one of them: Bitlotto. The choice was simple, as it is the easiest offered type of game: on each day exactly one number is drawn at random. You took notes the results of draws in consecutive days and obtained a sequence . You are sure that there is some pattern in this sequence, especially in intervals of consecutive days. Your family still does not believe you, so the only way to convince them is to use solid math.

There are intervals of days of length . The interval starts at position , so it contains elements . The distance between two intervals is the number of mismatches on their corresponding positions. In other words, for the and the interval it is the number of positions such that and are different. Finally, we define two intervals to be -similar if their distance is at most .

There is a fixed sequence and an integer . You are given queries. In every query, you are given an integer and for each of the intervals you must find the number of intervals of the same length that are -similar to this interval (not counting this interval itself).

Input

The first line of the standard input contains two space-separated integers and , the number of days and the length of the analysed intervals. The second line contains space-separated integers , where is the number that was drawn on the day.

The third line contains an integer , the number of queries. Each of the next lines contains an integer , the similarity parameter for the query.

Output

Print lines. The line should contain space-separated integers that are the answer to the query. The number in a line should be the number of other intervals that are -similar to the interval.

The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

Sample Input

6 2
1 2 1 3 2 1
2
1
2

Sample Output

2 1 1 1 1
4 4 4 4 4

Explanation for Sample Output

In the example above there are five intervals of length :

• the first interval contains the numbers
• the second contains
• the third contains
• the fourth contains
• the fifth contains

There are two queries.

The first query has . The first and the third interval — and — differ only on the second position, so the distance between them is . Similarly, the first and fourth interval — and — differ only on the first position, so the distance is . These are the only two intervals that are -similar to the first interval, so the first printed number is .

In the second query we are given . All pairs of intervals are -similar.