[CEOI2018] Lottery

译自 CEOI2018 Day1 T3. [Lottery](https://ceoi2018.pl/wp-content/uploads/2018/08/lot.pdf)。

**请注意特殊的内存限制。** 长期以来，你一直是 Bytelotto 的忠实粉丝，但你的家人一直告诉你所有这样的游戏都是在浪费钱。你觉得这肯定是因为他们缺少技巧。你有一个很棒的计划，每个人都将很快看到你赢得游戏。 游戏类型很多，你对其中之一感兴趣：Bitlotto。游戏规则很简单，每天随机抽取一个数字作为中奖数字。你记下了连续 $n$ 天的中奖数字 $a_1, a_2, \ldots, a_n$。你确信这当中存在某种规律，尤其是连续 $l$ 天的区间中。你的家人仍然不相信你，所以说服他们的唯一方法是可靠的数学。 一共有 $n-l+1$ 个长度为 $l$ 的区间。第 $i$ 个区间从 $i$ 开始，因此它包含元素 $a_i, a_{i+1}, \ldots, a_{i+l-1}$。定义两个区间的距离为他们对应位置上的数字不相等的数量。形式化地说，第 $x$ 个区间与第 $y$ 个区间的距离为满足 $a_{x+i}\ne a_{y+i}$ 的位置 $i\ (0\le i < l)$ 的数量。然后我们定义两个区间是 $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$，表示第 $j$ 个询问的相似参数。

输出 $q$ 行，第 $j$ 行包含 $n-l+1$ 个空格隔开的整数，表示第 $j$ 个询问的答案。一行中的第 $i$ 个数表示与第 $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$； - 第二个区间包含 $2$ $1$； - 第三个区间包含 $1$ $3$； - 第四个区间包含 $3$ $2$； - 第五个区间包含 $2$ $1$。 共有两个询问。 第一个询问 $k=1$。第一个和第三个区间——$1$ $2$ 和 $1$ $3$——只有第二个位置不同，所以他们的距离为 $1$。类似地，第一个和第四个区间——$1$ $2$ 和 $3$ $2$——只有第一个位置不同，所以他们的距离为 $1$。与第一个区间 $1$-相似的区间只有这两个，所以第一个数输出 $2$。 第二个询问 $k=2$，所有区间都是 $2$-相似的。 #### 数据规模与约定 对于 $100\%$ 的数据，$1\le n\le 10^4,\ 1\le a_i\le 10^9,\ 1\le q\le 100,\ 0\le k_j\le l$。 所有测试数据被划分成若干个有附加限制的子任务，每个子任务中包含若干测试点。 | 子任务 | 附加限制 | 分值 | | :--------: | :------------: | :--: | | $1$ | $n \le 300$ | $25$ | | $2$ | $n \le 2000$ | $20$ | | $3$ | $q=1, k_1=0$ | $20$ | | $4$ | $q=1$ | $15$ | | $5$ | 无附加限制 | $20$ |