题目描述

译自 CEOI2018 Day1 T3. Lottery

你是一位忠实的彩票迷，但你的家人一直告诉你玩彩票浪费金钱。在你看来，他们一定是缺乏技巧，因此你决定用事实证明你的实力。

在诸多的彩票类型中，你最喜欢 Bitlotto 这种彩票。这种彩票是所有彩票中规则最简单的——每天随机抽取一个数字作为中奖号码。你记下了连续 $n$ 天的获奖结果 $a_1, a_2, \ldots, a_n$。你确信这当中存在某种规律，尤其是那些长度为 $l$ 天的连续区间。你的家人并不相信你说的话，因此你需要用数据来说服他们。

一共有 $n-l+1$ 个长度为 $l$ 天的连续区间。第 $i$ 个长度为 $l$ 的区间包含 $a_i, a_{i+1}, \ldots,a_{i+l-1}$ 这些元素。我们定义两个区间的距离是两个区间对应位置值不相同的数量。形式化地说，第 $i$ 个区间和第 $j$ 个区间的距离为：

$$\sum_{k=1}^{l}[a_{i+k-1} \neq a_{j+k-1}]$$

如果两个区间的距离不超过 $k$，则称这两个区间是 $k$ - 相似 的。

现在给出连续 $n$ 天的获奖结果和 $q$ 个询问，每个询问给出一个整数 $k_j$，你需要对序列中的每个长度为 $l$ 的区间，求出与该区间 $k_j$ - 相似 的区间个数（该区间本身不计算在内）。

输入格式

第一行两个整数 $n,l$，分别为天数和你关心的区间长度。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 为第 $i$ 天的中奖号码。

第三行一个整数 $q$，代表询问的数量。

接下来 $q$ 行，每行一个整数 $k_j$。

输出格式

输出 $q$ 行。第 $j$ 行输出 $n-l+1$ 个整数，其中第 $j$ 行的第 $i$ 个整数代表对于第 $j$ 个询问，与第 $i$ 个区间 $k_j$ - 相似的区间个数。

样例

6 2
1 2 1 3 2 1
2
1
2

2 1 1 1 1
4 4 4 4 4

整个序列有五个长度为 $2$ 的区间。

对于第一个询问，第一个区间（$1,2$）和第三个区间（$1,3$）仅在第二个位置上不同，因此它们的距离为 $1$。同理，第一个区间（$1,2$）和第四个区间（$3,2$）仅在第一个位置上不同，因此它们的距离也为 $1$。容易看出，第一个区间只和这两个区间是 $1$ - 相似的。

对于第二个询问，容易看出任意两个区间都是 $2$ - 相似的。

数据范围与提示

所有数据均满足：$1 \leq l \leq n \leq 10^4$，$1 \leq a_i \leq 10^9$，$1 \leq q \leq 100$，$0 \leq k_j \leq l$。