Explosive Materials

You have taken a contract to transport explosives. You have $n$ trucks, and the $i$-th truck has capacity $x_i$.

For each truck you must plan how to pack it with explosives. Every truck has to be packed exactly full with explosives, because otherwise the materials may be damaged during transport. You have $k$ types of explosives with distinct sizes, where the $i$-th type has size $y_i$, and you can produce as much of each type as you need. Because loading and unloading trucks quickly matters, you want to use as few units of explosive as possible to fill a truck.

For each truck, compute the minimum number of explosive units needed to fill it exactly.

The first line contains two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 100$), the number of trucks and the number of explosive types. Each of the next $k$ lines contains the size $y_i$ of one explosive type ($1 \le y_i < 10^5$). Any two types have distinct sizes. Each of the next $n$ lines contains the capacity $x_i$ of one truck ($10^{10} \le x_i \le 10^{17}$).

Print $n$ lines. On the $i$-th line print $w_i$, the minimum number of explosive units needed to fill the $i$-th truck exactly, or the single word NIE if it is impossible.