JM的太爷爷的太爷爷的太爷爷……的太爷爷喜欢攒零钱,并把攒零钱作为祖训传承至今,现在已经攒了整整一箱子的硬币,JM清点了一下发现箱子里一共有 nnn 枚硬币。众所周知,古代的钱币放到现在都很值钱,所以这些硬币的价值并不相同。不过,由于寒域爷施了石志魔法,这些硬币的价值都是 222 的幂次。也就是说,对于任意的第 iii 枚硬币,其价值 aia_iai 一定满足 ai=2da_i = 2^dai=2d ,其中 ddd 是某个非负整数。
现在,石乐志的JM想拿这些硬币去买菜,他有 qqq 种想买的菜。因为石乐志,JM认为硬币的价值并不重要,而硬币的数量是最重要的。所以在买菜之前,他想事先知道,对于每种价格为 bjb_jbj 的菜,他最少需要用掉多少枚硬币才能将其买下。另外,由于JM有强迫症,他不希望他在买菜的时候还需要找零。
他希望你帮他分别计算买这 qqq 种菜的所需硬币数。注意,是分别计算,每种菜的求解之间是互相独立的。
第一行两个正整数 nnn 和 qqq ,表示JM的硬币数和JM想买的菜的种类数。
接下来一行 nnn 个正整数 aia_iai ,表示每个硬币的价值。输入保证 ai=2da_i = 2^dai=2d ,其中 ddd 是某个非负整数。
接下来 qqq 行,每行一个正整数 bjb_jbj ,表示每种菜的价格。
输出 qqq 行,每行一个正整数,表示买下每种菜所需的最少硬币个数。如果无论如何也无法凑齐价格(注意不能找零),则输出 −1-1−1 。
3 5 1 1 4 1 2 3 4 5
1 2 -1 1 2
1≤n, q≤2⋅1051 \le n,\ q \le 2 \cdot 10^51≤n, q≤2⋅105
1≤ai, bj≤2⋅1091 \le a_i,\ b_j \le 2 \cdot 10^91≤ai, bj≤2⋅109