시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 10 6 5 55.556%

문제

Archaeologists have just deciphered hieroglyphs on walls of a pyramid. The writings on one of the walls describe $N$ sacred numbers. All numbers which are divisible by at least one of these numbers are also sacred.

The writings on $M$ other walls claim that the $Q_i$-th lowest sacred number has magic properties. The archaeologists would like to know which numbers have the magic properties. Could you help them with that?

You are given $N$ positive integers $A_1, A_2, \ldots, A_N$ and $M$ positive integers $Q_1, Q_2, \ldots, Q_M$. For each $i \in \{ 1, 2, \ldots, M \}$ find the $Q_i$-th lowest positive integer which is divisible by at least one of the integers $A_1, A_2, \ldots, A_N$.

입력

The first line of the input contains two integers $N$ a $M$. The second line contains space-separated integers $A_1$, $A_2$, $\ldots$, $A_N$. Then, $M$ lines follow. Each of them contains an integer $Q_i$.

  • It holds $1 \leq N \leq 15$ and $1 \leq M \leq 50$.
  • For all $i \in \{ 1, 2, \ldots, N \}$ it holds $2 \leq A_i \leq 10^{18}$.
  • For the product of these numbers it holds $A_1 \cdot A_2 \cdot \ldots \cdot A_N \leq 10^{18}$.
  • For all $i \in \{ 1, 2, \ldots, M \}$ it holds $1 \leq Q_i \leq 10^{18}$.
  • Each number on the output is lower than or equal to $10^{18}$.
  • Furthermore, in 10 % of the testcases $Q_1, Q_2, \ldots, Q_M \leq 10^6$. Furthermore, in 30 % of the testcases $N \leq 2$.

출력

Output $M$ lines. The $i$-th line should contain the $Q_i$-th lowest positive integer which is divisible by at least one of the integers $A_1, A_2, \ldots, A_N$.

예제 입력 1

5 5
2 5 7 10 11
1
2
3
10
20

예제 출력 1

2
4
5
14
28

예제 입력 2

2 1
70 100
5

예제 출력 2

210

힌트