/**
* Notes during contest.
*
* ------ A ------
* Looks like a dp, and the score distribution is interesting too.. Sort the machines
* and orders by their clock speed. By greedy arguments, if we've seletected the
* subset of orders & machines, we sort the clock speed in order and assign them.
* [S3] is the one that gave me the idea: we first sort orders & machines, then use
* O(nm) dp on prefixes. Note that cores can be shared across orders, so we need an
* additional val in our dp state, which is the num of cores left. This val can at
* most be 50. Note that one should take a close look at the memory limit too: our dp
* sequence shouldn't take up too much memory.
*
* P.S. When about 1.5 hours were left, I left home. Technically I didn't finish the
* virtual contest.
*
* ------ B ------
* I think i've seen sth similar on luogu. First, let's assume that d >= 0 and i'll
* use the words "increase" & "decrease". If we wanna increase an interval by d, we
* can greedily increase a suffix (instead of just an interval in the middle). If we
* are to decrease an interval by d, we can greedily decrease a prefix. The two cases
* are symmetric, so we can assume that one always increase a suffix by 0 <= d <= x.
* And, if we're increasing a suffix, why don't we just do d=x? The rest is quite
* straight-forward.
*
* ------ C ------
* For k_j = 0, we have to find the num of times each interval appeared. This can be
* effectively done with str hashing. [S3] solved. [S1] is just brute-force: we can
* do a O(n^2) for loop, iterating over all pairs of starting pos, naively comparing
* the dist. of 2 substr. [S2] is a O(n^2) comparison between pairs of VALUES and
* apply a difference array.
* We're only looking for the num of mismatches. Let's compress the values (a_i:
* 10^9 -> 10^4).
* [After contest]
* I was so shocked after reading the solution. (Most people thought it was the
* easiest problem, yet it was the only problem on the 1st day that i couldn't finish
* myself!) Anyway, let dist[i][j] = dist. between the substr starting at i and the
* one starting at j. It turns out that a O(n^2) (time comp.) solution can pass! But
* we must optimize memory usage (O(n^2) memory is too much). The key is to not store
* dist[][].
* I computed dist[i][j] by iterating through j-i (from small to large). One may find
* that a lot of comparisons can be removed, e.g. we have:
* dist[i+1][j+1] = dist[i][j] + (sth) - (sth).
* Each time, a row of dist[][] is maintained, so we can answer all queries related
* to that pos. The impl looks kinda neat too~
*
* Time Complexity 1: O(nm * c_max + n * log(n) + m * log(m))
* Time Complexity 2: O(n * log(n))
* Time Complexity 3: O(n^2 + qn)
* Mem. Compleixty 3: O(nq)
* Implementation 2 (Full solution, memory optimized)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int> vec;
const int INF = 0x3f3f3f3f;
struct query_t {
int q, original_idx;
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, l, q;
std::cin >> n >> l;
vec values(n);
for (int_t k = 0; k < n; k++)
std::cin >> values[k];
std::cin >> q;
vec queries(q);
for (int_t i = 0; i < q; i++)
std::cin >> queries[i];
std::vector<vec> ans(n, vec(q, -1));
// Some 0s in dist[] isn't valid. This is because they don't repr real substrs.
// But anyway, they may become "real" with other pos k, so we keep those as
// "partial comparisons".
vec dist(2 * n - 1, 0);
// compare substr starting at 0 at 0+k, skip out of bound positions.
for (int k = -n + 1; k <= n - 1; k++) {
for (int i = 0; i < l; i++) {
if (0 <= i + k && i + k < n)
dist[k + (n - 1)] += (values[i] != values[i + k]);
}
}
for (int k = 0; k + l <= n; k++) {
// ans query for pos k
vec prefix_sum(l + 1, 0);
for (int i = -n + 1; i <= n - 1; i++) {
if (0 <= i + k && i + k + (l - 1) < n)
prefix_sum[dist[i + (n - 1)]]++;
}
for (int t = 1; t <= l; t++)
prefix_sum[t] += prefix_sum[t - 1];
for (int i = 0; i < q; i++)
ans[k][i] = prefix_sum[queries[i]] - 1;
// re-calculate dist[] for the next k
if (k != n - 1) {
for (int i = -n + 1; i <= n - 1; i++) {
// dist_new[i] = dist[i] + (values[k+i+l] != values[k+l])
// - (values[k+i] != values[k])
if (0 <= k + l && k + l < n && 0 <= k + i + l && k + i + l < n)
dist[i + (n - 1)] += (values[k + i + l] != values[k + l]);
if (0 <= k + i && k + i < n)
dist[i + (n - 1)] -= (values[k + i] != values[k]);
}
}
}
for (int i = 0; i < q; i++) {
for (int j = 0; j + l <= n; j++)
std::cout << ans[j][i] << ' ';
std::cout << '\n';
}
}
