Harry Potter and the Prisoner of Azkaban
Tag(s):

Easy-Medium, Easy-Medium

Problem
Editorial
Analytics

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.

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

SAMPLE INPUT
5 5
1 5 8 9 16
4
12
18
17
8
SAMPLE OUTPUT
4
4
9
1
8
Time Limit: 0.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor Challenge Name

Epiphany 6.2

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Greedy Algorithms