Description

Please note the special memory limit.

For a long time, you have been a loyal fan of Bytelotto, but your family has always told you that all such games are a waste of money. You think this is surely because they lack skill. You have a great plan, and everyone will soon see you win the game.

There are many types of games, and you are interested in one of them: Bitlotto. The rules are simple: every day, one number is drawn at random as the winning number. You recorded the winning numbers for $n$ consecutive days: $a_1, a_2, \ldots, a_n$. You are sure there is some pattern in them, especially in intervals of $l$ consecutive days. Your family still does not believe you, so the only way to convince them is solid mathematics.

There are $n - l + 1$ intervals of length $l$. The $i$-th interval starts at $i$, so it contains the elements $a_i, a_{i+1}, \ldots, a_{i+l-1}$. Define the distance between two intervals as the number of positions where the numbers at the corresponding positions are different. Formally, the distance between the $x$-th interval and the $y$-th interval is the number of positions $i\ (0 \le i < l)$ such that $a_{x+i} \ne a_{y+i}$. Then we say that two intervals are $k$-similar if and only if their distance is at most $k$.

Now you are given the winning numbers for $n$ consecutive days and $q$ queries. Each query gives an integer $k_j$. For each interval of length $l$ in the sequence, you need to compute how many other intervals are $k_j$-similar to it (excluding itself).

Input Format

The first line of standard input contains two integers $n, l$, representing the number of days and the interval length you want to analyze.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ separated by spaces, where $a_i$ is the winning number on day $i$.

The third line contains one integer $q$, the number of queries.

The next $q$ lines each contain one integer $k_j$, the similarity parameter for the $j$-th query.

Output Format

Output $q$ lines. The $j$-th line contains $n - l + 1$ integers separated by spaces, which are the answers for the $j$-th query. The $i$-th number in a line is the number of intervals that are $k_j$-similar to the $i$-th interval, excluding itself.

6 2
1 2 1 3 2 1
2
1
2

2 1 1 1 1
4 4 4 4 4

Hint

Sample Explanation

The whole sequence has five intervals of length $2$:

• The first interval contains $1$ $2$.
• The second interval contains $2$ $1$.
• The third interval contains $1$ $3$.
• The fourth interval contains $3$ $2$.
• The fifth interval contains $2$ $1$.

There are two queries.

For the first query, $k = 1$. The first and the third intervals, $1$ $2$ and $1$ $3$, differ only at the second position, so their distance is $1$. Similarly, the first and the fourth intervals, $1$ $2$ and $3$ $2$, differ only at the first position, so their distance is $1$. There are only these two intervals that are $1$-similar to the first interval, so the first output number is $2$.

For the second query, $k = 2$, all intervals are $2$-similar.

Constraints

For $100\%$ of the data, $1 \le n \le 10^4$, $1 \le a_i \le 10^9$, $1 \le q \le 100$, $0 \le k_j \le l$.

All testdata is divided into several subtasks with additional constraints, and each subtask contains several test points.

Translated by ChatGPT 5