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), gcd(M, arr), ........ , 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.
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.
Print Q lines containing an integer K, pertaining the particular values of M.