长期以来，你一直是 Bytelotto 的忠实粉丝。与此同时，你的家人一直告诉你，这类游戏纯属浪费钱。你确信这是因为他们缺乏技巧！你有一个绝妙的计划，很快大家就会看到你赢得比赛。

游戏有很多种。你对其中一种很感兴趣：Bitlotto。选择很简单，因为它是最容易上手的游戏类型：每天随机抽取一个数字。你记录了连续 $n$ 天的抽奖结果，得到了一个序列 $a_1, a_2, \dots, a_n$。你确信这个序列中存在某种模式，特别是在长度为 $l$ 的连续区间内。你的家人仍然不相信你，所以说服他们的唯一方法就是使用严谨的数学。

共有 $n - l + 1$ 个长度为 $l$ 的天数区间。第 $i$ 个区间从位置 $i$ 开始，包含元素 $a_i, a_{i+1}, \dots, a_{i+l-1}$。两个区间之间的距离是它们对应位置上不匹配的数量。换句话说，对于第 $x$ 个区间和第 $y$ 个区间，距离是满足 $a_{x+i} \neq a_{y+i}$ 的位置 $i$ ($0 \le i < l$) 的数量。最后，如果两个区间的距离最多为 $k$，我们定义它们为 $k$-相似。

给定一个固定的序列和一个整数 $l$。你有 $q$ 次查询。在每次查询中，给定一个整数 $k_j$，对于 $n - l + 1$ 个区间中的每一个，你必须找出与该区间 $k_j$-相似的相同长度的区间数量（不包括该区间本身）。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $l$ ($1 \le l \le n \le 10\,000$)，表示天数和分析区间的长度。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，其中 $a_i$ 是第 $i$ 天抽取的数字。

第三行包含一个整数 $q$ ($1 \le q \le 100$)，表示查询次数。接下来的 $q$ 行，每行包含一个整数 $k_j$ ($0 \le k_j \le l$)，表示第 $j$ 次查询的相似度参数。

输出格式

输出 $q$ 行。第 $j$ 行应包含 $n - l + 1$ 个空格分隔的整数，作为第 $j$ 次查询的答案。行中的第 $i$ 个数字应为与第 $i$ 个区间 $k_j$-相似的其他区间的数量。

样例

样例输入 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-相似的。

子任务