#1023. 1-02D. JM的祖传零钱箱

内存限制:512 MiB 时间限制:1875 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

JM的太爷爷的太爷爷的太爷爷……的太爷爷喜欢攒零钱,并把攒零钱作为祖训传承至今,现在已经攒了整整一箱子的硬币,JM清点了一下发现箱子里一共有 nn 枚硬币。众所周知,古代的钱币放到现在都很值钱,所以这些硬币的价值并不相同。不过,由于寒域爷施了石志魔法,这些硬币的价值都是 22 的幂次。也就是说,对于任意的第 ii 枚硬币,其价值 aia_i 一定满足 ai=2da_i = 2^d ,其中 dd 是某个非负整数。

现在,石乐志的JM想拿这些硬币去买菜,他有 qq 种想买的菜。因为石乐志,JM认为硬币的价值并不重要,而硬币的数量是最重要的。所以在买菜之前,他想事先知道,对于每种价格为 bjb_j 的菜,他最少需要用掉多少枚硬币才能将其买下。另外,由于JM有强迫症,他不希望他在买菜的时候还需要找零。

他希望你帮他分别计算买这 qq 种菜的所需硬币数。注意,是分别计算,每种菜的求解之间是互相独立的。

输入格式

第一行两个正整数 nnqq ,表示JM的硬币数和JM想买的菜的种类数。

接下来一行 nn 个正整数 aia_i ,表示每个硬币的价值。输入保证 ai=2da_i = 2^d ,其中 dd 是某个非负整数。

接下来 qq 行,每行一个正整数 bjb_j ,表示每种菜的价格。

输出格式

输出 qq 行,每行一个正整数,表示买下每种菜所需的最少硬币个数。如果无论如何也无法凑齐价格(注意不能找零),则输出 1-1

样例

样例输入

3 5
1 1 4
1
2
3
4
5

样例输出

1
2
-1
1
2

数据范围与提示

1n, q21051 \le n,\ q \le 2 \cdot 10^5

1ai, bj21091 \le a_i,\ b_j \le 2 \cdot 10^9