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

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

题目描述

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

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

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

输入格式

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

接下来一行 个正整数 ,表示每个硬币的价值。输入保证 ,其中 是某个非负整数。

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

输出格式

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

样例

样例输入

3 5
1 1 4
1
2
3
4
5

样例输出

1
2
-1
1
2

数据范围与提示