题目描述

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

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

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

输入格式

• 第一行两个整数 $n,m$。
• 第二行 $n$ 个整数 $a_1\sim a_n$。
• 第三行一个整数 $q$。
• 接下来 $q$ 行，每行一个整数 $x$。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

5
4
4
3
3

说明/提示

总共 $20$ 个测试点：

• 对于测试点 $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$。