题目描述

现在有 $n$ 个大小范围在 $1\sim m$ 中的整数 $a_1\sim a_n$，并且你获得了一项魔法能力。 施加一次魔法能力后，可以将两个相同的数字合并成一个数字，并且这个数字为原来的数字 $+1$，例如：

• 有 $2,2$ 这两个数字，施加一次魔法能力后可以将这两个数字合并成一个数字 $3$。

现在有 $q$ 次询问，每次询问给你一个整数 $x$，你可以施加任意次数魔法能力，问你这 $n$ 个整数最多能得到多少个整数 $x$

输入格式

从文件 fit.in 中读取数据。

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1\sim a_n$。

第三行一个整数 $q$。

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

输出格式

输出到文件 fit.out 中。

输出 $q$ 行，对于每个询问，输出对应的答案。

10 4
1 1 1 2 1 3 4 1 2 3
5
1
2
3
4
4

5
4
4
3
3

样例输入输出 2

见 2.in 与 2.ans

数据规模与约定

• 对于测试点 $1\sim 4$：$1\le n \le 10,1\le m\le 10,1\le a_i\le m,1\le q\le 10,1\le x\le m$。
• 对于测试点 $5\sim 6$：$1\le n\le 10^6,m=1,a_i=1,q=1,x=1$。
• 对于测试点 $7\sim 8$：$1\le n\le 10^6,m=5,1\le a_i\le m,1\le q\le m,1\le x\le m$。
• 对于测试点 $9\sim 20$：$1\le n\le 10^6,1\le m\le 10^6,1\le a_i\le m,1\le q\le m,1\le x\le m$。