P6360 [CEOI 2018] Lottery

Translated from CEOI 2018 Day 1 T3. [Lottery](https://ceoi2018.pl/wp-content/uploads/2018/08/lot.pdf).

**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).

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 $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.

#### 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. | Subtask | Additional Constraints | Score | | :--------: | :------------: | :--: | | $1$ | $n \le 300$ | $25$ | | $2$ | $n \le 2000$ | $20$ | | $3$ | $q = 1, k_1 = 0$ | $20$ | | $4$ | $q = 1$ | $15$ | | $5$ | No additional constraints | $20$ | Translated by ChatGPT 5