Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Jhamela, Once Again

By AST_TheCoder · Limits 1s, 128 MB

You are given n positive integers as an array. Also, you are given an integer k. Now, try to find a subsequence of the array that (LCM - GCD) of that subsequence equals to k. You don’t have to print the subsequence, just print whether it is possible to find a subsequence with given condition or not!

Note: Here, LCM means Least common multiple and GCD means Greatest common divisor. Also subsequence means a new array which can be generated by deleting some values of initial array without changing the order. GCD & LCM of single number are same and equal to the number of itself.

Input

You have to answer T independent queries.
First line contains two integers n & k, the length of the array and the value of (LCM - GCD). Second line contains n positive integers as an array a. Let, the value at ith position is ai.

Subtasks

Subtask #1 (10 points)
1 ≤ T ≤ 10
1 ≤ n ≤ 9
0 ≤ k ≤ 102
1 ≤ ai ≤ 102

Subtask #2 (30 points)
1 ≤ T ≤ 10
1 ≤ n ≤ 103
0 ≤ k ≤ 104
1 ≤ ai ≤ 104

Subtask #3 (60 points)
1 ≤ T ≤ 10
1 ≤ n ≤ 105
0 ≤ k ≤ 105
1 ≤ ai ≤ 105

Output

Print “YES”, if it is possible to find a subsequence which (LCM - GCD) equals to k. Otherwise, print “NO”.

Print them without quotes with a newline. And, try to use faster IO as the dataset is huge.

Sample

InputOutput
5
5 3
2 4 8 3 6
3 22
6 8 12
3 20
6 8 12
3 6
6 8 12
3 10
6 8 12
YES
YES
YES
YES
NO

In first case, GCD of {3, 6} is 3 and LCM of same subsequence is 6. So, (LCM - GCD) is 3 here.
In second case, GCD of {6, 8, 12} is 2 and LCM of same subsequence is 24. So, (LCM - GCD) is 22 here.
In third case, GCD of {8, 12} is 4 and LCM of same subsequence is 24. So, (LCM - GCD) is 20 here.
In fourth case, GCD of {6, 12} is 6 and LCM of same subsequence is 12. So, (LCM - GCD) is 6 here.
In last case, there’s no subsequence which difference of LCM and GCD equals to 10.


Discussion

Statistics


41% Solution Ratio

AST_TheCoderEarliest, 1M ago

Ashraful_jnuFastest, 0.1s

serotoninLightest, 131 kB

serotoninShortest, 792B

Submit

Login to submit

Editorial

For the first subtask, just find out all of the subsequences. In this case, the number of subsequenc...