#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int N = 2000 + 3, Q = 100 + 3, N3 = 1e4 + 3;
const ll base = 1e9 + 7, mod = 1e9 + 9;
int n, l;
int a[N];
int q, k[Q];
int dp[N][N];
void subtask1() {
for (int i = 1; i <= n - l + 1; ++i)
for (int j = 1; j <= n - l + 1; ++j) if (j != i) {
int diff(0);
for (int k = 0; k < l; ++k) diff += a[i + k] != a[j + k];
for (int k = diff; k <= l; ++k) ++dp[i][k];
}
for (int i = 0; i < q; ++i)
for (int j = 1; j <= n - l + 1; ++j) cout << dp[j][k[i]] << " \n"[j == n - l + 1];
}
void subtask2() {
for (int dist = 1; dist <= n - l; ++dist) {
int i(1), j(1 + dist), diff(0);
for (int k = 0; k < l; ++k) diff += a[i + k] != a[j + k];
for (; j <= n - l + 1; ++i, ++j) {
++dp[i][diff], ++dp[j][diff];
diff -= a[i] != a[j];
diff += a[i + l] != a[j + l];
}
}
for (int i = 1; i <= n; ++i)
for (int k = 1; k <= l; ++k) dp[i][k] += dp[i][k - 1];
for (int i = 0; i < q; ++i)
for (int j = 1; j <= n - l + 1; ++j) cout << dp[j][k[i]] << " \n"[j == n - l + 1];
}
ll h[N3], pw[N3];
int get(int l, int r) {
return (h[r] - h[l - 1] * pw[r - l + 1] + mod * mod) % mod;
}
void subtask3() {
pw[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = (h[i - 1] * base + a[i]) % mod;
pw[i] = pw[i - 1] * base % mod;
}
unordered_map<int, int> mp;
for (int i = 1; i <= n - l + 1; ++i)
++mp[get(i, i + l - 1)];
for (int i = 1; i <= n - l + 1; ++i)
cout << mp[get(i, i + l - 1)] - 1 << " \n"[i == n - l + 1];
}
int ans[N3];
void subtask4() {
for (int dist = 1; dist <= n - l; ++dist) {
int i(1), j(1 + dist), diff(0);
for (int k = 0; k < l; ++k) diff += a[i + k] != a[j + k];
for (; j <= n - l + 1; ++i, ++j) {
if (diff <= k[0]) ++ans[i], ++ans[j];
diff -= a[i] != a[j];
diff += a[i + l] != a[j + l];
}
}
for (int i = 1; i <= n - l + 1; ++i)
cout << ans[i] << " \n"[i == n - l + 1];
}
int tmp[Q], inv[N3];
int dp2[N3][Q];
void subtask5() {
copy(k, k + q, tmp + 1);
sort(tmp, tmp + q + 1);
int cnt = unique(tmp, tmp + q + 1) - tmp;
for (int i = 0; i < cnt; ++i)
inv[tmp[i]] = i;
for (int dist = 1; dist <= n - l; ++dist) {
int i(1), j(1 + dist), diff(0), ptr(0);
for (int k = 0; k < l; ++k) {
diff += a[i + k] != a[j + k];
if (diff > tmp[ptr]) ++ptr;
}
for (; j <= n - l + 1; ++i, ++j) {
++dp2[i][ptr], ++dp2[j][ptr];
diff -= a[i] != a[j];
if (diff < tmp[ptr]) --ptr;
diff += a[i + l] != a[j + l];
if (diff > tmp[ptr]) ++ptr;
}
}
for (int i = 1; i <= n; ++i)
for (int k = 1; k < cnt; ++k) dp2[i][k] += dp2[i][k - 1];
for (int i = 0; i < q; ++i)
for (int j = 1; j <= n - l + 1; ++j)
cout << dp2[j][inv[k[i]]] << " \n"[j == n - l + 1];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> l;
for (int i = 1; i <= n; ++i) cin >> a[i];
cin >> q;
for (int i = 0; i < q; ++i)
cin >> k[i];
if (n <= 300) subtask1();
else if (n <= 2000) subtask2();
else if (q == 1) {
if (k[0] == 0) subtask3();
else subtask4();
}
else subtask5();
}
