Pyramid

Archaeologists have deciphered the hieroglyphs carved on the walls of a pyramid. One wall lists $N$ sacred numbers. Every positive integer divisible by at least one of those $N$ numbers is sacred as well.

The writings on $M$ other walls say that the $Q_i$-th smallest sacred number has magic properties. The archaeologists want to know which numbers those are.

You are given positive integers $A_1, A_2, \ldots, A_N$ and positive integers $Q_1, Q_2, \ldots, Q_M$. For each $i$, find the $Q_i$-th smallest positive integer that is divisible by at least one of $A_1, A_2, \ldots, A_N$.

The first line contains two integers $N$ and $M$. The second line contains the integers $A_1, A_2, \ldots, A_N$ separated by spaces. Each of the next $M$ lines contains one integer $Q_i$.

• $1 \le N \le 15$ and $1 \le M \le 50$
• $2 \le A_i \le 10^{18}$ for every $i$
• $A_1 \times A_2 \times \cdots \times A_N \le 10^{18}$
• $1 \le Q_i \le 10^{18}$ for every $i$
• Every number in the output is at most $10^{18}$.
• In 10% of the test cases $Q_1, Q_2, \ldots, Q_M \le 10^6$. In 30% of the test cases $N \le 2$.

Print $M$ lines. Line $i$ contains the $Q_i$-th smallest positive integer that is divisible by at least one of $A_1, A_2, \ldots, A_N$.