DSWEETS - Distributing sweets

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.


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

hide comments
2015-03-30 19:56:30 rinzler
awesome problem :D
2015-03-05 18:54:07 utkarsha gaumat
finally ac
2015-03-05 10:44:00 Bhavik
@utkarsha: that's part of question,you need to figure it out
2015-03-04 19:01:37 utkarsha gaumat
if all marks are zero and number of weets is non zero then??
2015-02-04 22:16:00 Walid Amin
@Vamsi Krishna Avula
Thank you :)
2015-01-27 09:48:46 Vamsi Krishna Avula
wow, very tricky problem!
2015-01-11 22:17:34 Walid Amin
@Tjandra Satria Gunawan
thank you for the appreciation :D
2015-01-11 10:01:54 (Tjandra Satria Gunawan)(曾毅昆)
tricky problem, test cases are strong :-)
2015-01-05 15:42:19 Walid Amin
@Francky
Updated :D
my worst acc complexity O(nlogn) code in C - it can be solved in O(n) - passes in 1 second and i extended time into 28 seconds (for all test cases) :D
I expect no TLE for Python :D
and i am keeping an eye on comments
Thank you Francky

Last edit: 2015-01-05 15:43:28
2015-01-05 14:58:42 Walid Amin
@Francky
i modified the test cases and removed many of them
the input size now is 26 MB
my C code passes in 1 second in all cases (from 9 seconds)
by using C++ it passes in 3.5 seconds (from 9 seconds)
they are three cases (2 seconds, 2 seconds, 5 seconds)
i will extend it but i have no experience with Python so how much i have to extend the time please
and thank you Francky for your time :D
--francky--> For that kind of problem, consider Python approx ×15 to ×20 slower than C (depends on code opti, on C and/or on Python). Better is to allow ×20 your C code.
Did you try a bad C code, and its expected time ? (even on a smaller input).

Last edit: 2015-01-05 15:10:58
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.