DSWEETS - Distributing sweets

no tags 

One day AAST students had their marks in “Scientific Thinking” and most of students had bad marks.

So the lecturer want to give them something to make them happy so he checked his bag and found n sweets, so he decided to distribute them to his students by this way:

  1. Everyone gets an integer number of sweets and at least one sweet.
  2. He wanted the ratio between mark of a student and number of sweets this student gets equal to the ratio between these of any other student. (for all students: mark of a student / number of sweets he gets = constant, where number of sweets he gets are more than zero and this constant could be any real number).
  3. It must be distributed following last conditions such that no sweets remain.

Example: if two students x and y, x has 5 marks and y has 10 marks, so y must get double the number of sweets x will get which is the number of sweets x will get is at least one.

But Mohamed Ramzy is the most student joking in his lecture so that he decided to punish him and asked him to distribute the sweets, but Ramzy doesn’t know if it is possible to distribute the sweets following the conditions the lecturer stated so he asked you to help him. 

Input

First line contains an integer t, the number of test cases.

For each test case, it begins with two integers n and m, the number of sweets and the number of students respectively. The next line contains m integers, the marks of the students, such that the first mark belongs to the first student , the second mark belongs to the second students and so on…

Edit: There is no blank line in the input file

Output

For each test case print one line: “YES” if it is possible to distribute it following the conditions, “NO” otherwise.

Constraints

0 <= n <= 1000000
0 < m <= 1000000
0 <= mark of each student <= 1000000

Example

Input:
3
5 4
1 1 1 1
4 4
1 1 1 1
3 2
1 2

Output:
NO
YES
YES

Explanation

First test case there is no possible way to distribute the sweets following the conditions stated.

In the second and third test case it is possible to distribute the sweets such that the constant will be one.


hide comments
smso: 2019-03-06 16:02:13

1
6 4
0 0 0 0

output from spojtoolkit:
YES

Each one should get 1 sweet with 2 sweets remain. This is not consistent with the third condition as mentioned in the problem!

Sushovan Sen: 2016-05-14 14:14:15

what should be output for:
1
5 3
0 2 3
??
Any other tricky case?

Last edit: 2016-06-28 13:28:17
bunnycoder: 2015-10-24 09:23:50

After a dozen of wrong answers finally AC never work on decimals and precision lesson learnt

Rushikesh Potdar: 2015-08-26 06:57:53

can anybody tell me what is test case 4?? pls....

harshit sharma: 2015-07-18 19:40:31

good problem easy yet interesting...worth solving it

Last edit: 2015-07-18 20:46:09
black_t: 2015-07-18 09:09:05

take : long long int every variable .... cause me 5 WA

DHEERAJ KUMAR: 2015-07-06 00:58:47

Too many WA's
anyone help please :(

yash agarwal: 2015-06-29 08:25:55

silly mistakes caused me too many WA's..

Deeksha: 2015-06-18 22:35:44

AC in 1st go.... top of d table :D

Shubham Sinha: 2015-04-11 12:55:49

getting wa on test case 4 can anyone help ??


Added by:Walid Amin
Date:2014-12-27
Time limit:4s-20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64