You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

区间距离

题目描述

请注意特殊的内存限制。

定义两个长度为 $l$ 的序列 $A$ 和 $B$ 的距离为使得 $a_i\ne b_i$ 的满足 $1\le i\le l$ 的 $i$ 的个数。

现在给定一个数组 $a_1,a_2,...,a_n$ ，它显然有 $n-l+1$ 个长为 $l$ 的连续子序列，其中第 $k$ 个为 $a_k,a_{k+1},...,a_{k+l-1}$ 。

现在有 $q$ 次询问，每次询问给定一个整数 $k_j$ ，你需要对序列中的每个长度为 $l$ 的区间，求出与该区间距离不超过 $k_j$ 的区间个数（不包括本身）。

输入格式

输入的第一行包含两个整数 $n,l$，分别表示数组长度和指定长度。

第二行包含 $n$ 个空格隔开的整数 $a_1, a_2, \ldots, a_n$，$a_i$ 表示数组。

第三行包含一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行包含一个整数 $k_j$，表示第 $j$ 个询问的距离范围。

输出格式

输出 $q$ 行，第 $j$ 行包含 $n-l+1$ 个空格隔开的整数，表示第 $j$ 个询问的答案。一行中的第 $i$ 个数表示与第 $i$ 个区间距离不超过 $k_j$ 的不包括本身的区间数量。

样例 #1

样例输入 #1

6 2
1 2 1 3 2 1
2
1
2

样例输出 #1

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