Hermione Granger can be in many places at once, thanks to the Time Turner. But, do you know, there is a certain logic between the number of rotations of the hourglass and the time in seconds she can go back to. The Time Turner works according to an array of N integers which are a characteristic to the Time Turner. Now, for K rotations of the Time Turner, she can go M seconds back in time, where,

K = max( gcd(M, arr[0]), gcd(M, arr[1]), ........ , gcd(M, arr[N-1]) )

Now, given Q situations, for each situation, you need to help her find the number of rotations of the hourglass, K she should do to go back M seconds in time.

Input

First line contains two integers, N and Q.

Second line contains N integers which form the arr[].

Next Q lines contain an integer M, the time in seconds she wishes to go back.

Output

Print Q lines containing an integer K, pertaining the particular values of M.

Constraints

1<=N<=10^5

1<=Q<=10^5

1<=arr[i]<=10^6

1<=M<=10^6