409729: GYM103708 K Kilo Waste

A shelter for homeless people wants to buy $$$n$$$ kilograms of rice for their dinner, but the market only offers bags of rice in predefined weights, making hard for the shelter to buy rice without waste.

For example, if the shelter wanted to buy $$$10$$$ kilos of rice for the dinner and the available presentations at the market have bags of rice with $$$2$$$, $$$15$$$, and $$$7$$$ kilos, the shelter can buy exactly $$$10$$$ kilos buying 5 bags of 2 kilos and no rice will be wasted that night. However, if the shelter wanted to buy $$$5$$$ kilos, there is no way they can buy rice in a way there is no waste, in this case, the minimum waste they can achieve is $$$1$$$ (buying $$$3$$$ bags of $$$2$$$ kilos).

Given a list of rice sales presentations available at the market, and the amount of rice the shelter wants to buy for each of the next $$$k$$$ dinners, find the minimum rice waste the shelter can have for each dinner.

The first line of input contains two integer numbers separated by a space $$$k$$$, and $$$p$$$, ($$$1 \leq k \leq 10^5$$$, $$$1 \leq p \leq 50$$$) representing the number $$$k$$$ of dinners the shelter will make, and the number $$$p$$$ of presentations of rice the market sells. The second line of input contains $$$p$$$ integer numbers separated by space, where the $$$i$$$-th number represents the amount of rice $$$r_i$$$ ($$$1 \leq r_i \leq 100$$$) on the $$$i$$$-th rice presentation available at the market. Each of the next $$$k$$$ lines contains an integer number, where the $$$i$$$-th line represents the amount of rice $$$n_i$$$ ($$$1 \leq n_i \leq 5 \times 10^4$$$) the shelter needs to buy for the $$$i$$$-th dinner.

Print $$$k$$$ lines, where the $$$i$$$-th line contains a single integer number, the minimum rice waste the shelter can have after buying rice for the $$$i$$$-th dinner.

2 3
2 15 7
10
5

0
1

2 3
11 24 35
105
10

0
1

3 2
10 17
1
16
27

9
1
0