Exchanging money

4

12 votes
Greatest common divisor, Algorithms, GCD, Math, Number Theory
Problem

There are N types of money denomination in your country having values a1,a2,...,an. You went to a shop to buy a product worth Punits, predict whether is it possible to complete the purchase or not (You and the shopkeeper can choose notes of each denomination any number of times). You need to process Q queries for this. Print "YES" if it is possible to complete the purchase, else print "NO".

 

Input Format

  • First line contains two space-separated integers N and Q
  • Second line contains n space-separated integers a1,a2,...,an
  • Next Q lines contains the value of P for each query.

 

Constraints

1N105

1Q105

1ai109

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

For the first query, P=3, you give a note of 9 to the salesman and he returns 6 to you, hence the purchase completed successfully.

For the second query, P=4, there's no way to complete the purchase.

Editor Image

?