某小国知名银行的 ATM 机被安排为无法提供用户要求的任何金额。由于提款机(直接从ATM取款的设备)的尺寸有限以及ATM结构的一些特殊性,您最多可以从中取出k张钞票,并且钞票最多可以有两种不同的面额。
例如,如果一个国家使用面额为 10、50、100、500、1000 和 5000 伯尔的钞票,则在 k = 20 时,此类 ATM 可以给出 100,000 伯尔和 96,000 伯尔的总和,但不能给出 99,000 和 101,000 伯尔的总和布尔斯。
假设该国家/地区使用 n 种不同面额的钞票,并且您使用的 ATM 上每种类型的钞票数量不受限制。您知道白天您需要提取一定数量的现金 q 次。大家知道,当ATM机有多种取款方式时,它会选择需要最少张数的取款方式,如果无法完成则显示错误消息。确定q个现金提取请求中每一个的结果。
输入
第一行包含两个整数 n, k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 20)。
下一行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 107) — 该国使用的纸币面额。数字 ai 按严格递增的顺序排列。
下一行包含整数 q (1 ≤ q ≤ 20) — 您将提出的现金提取请求数。
接下来的 q 行包含数字 xi (1 ≤ xi ≤ 2·108) — 您要从 ATM 机提取的金额(以 burles 为单位)。
输出
对于每个提现请求,在一行中打印可以完成的最小账单数量,如果无法获得相应的金额,则打印 - 1。
示例
输入 #1
6 20 10 50 100 500 1000 5000 8 4200 100000 95000 96000 99000 10100 2015 9950
输出 #1
6 20 19 20 -1 3 -1 -1
输入 #2
5 2 1 2 3 5 8 8 1 3 5 7 9 11 13 15
输出 #2
1 1 1 2 2 2 2 -1