You are given a list of $n$ integers. You can perform the following operation: you choose an element $x$ from the list, erase $x$ from the list, and subtract the value of $x$ from all the remaining elements. Thus, in one operation, the length of the list is decreased by exactly $1$.

Given an integer $k$ ($k>0$), find if there is some sequence of $n-1$ operations such that, after applying the operations, the only remaining element of the list is equal to $k$.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 2\cdot 10^5$, $1 \leq k \leq 10^9$), the number of integers in the list, and the target value, respectively.

The second line of each test case contains the $n$ integers of the list $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases is not greater that $2 \cdot 10^5$.


-----Output-----

For each test case, print YES if you can achieve $k$ with a sequence of $n-1$ operations. Otherwise, print NO.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer).


-----Examples-----

Input
4
4 5
4 2 2 7
5 4
1 9 1 3 4
2 17
17 0
2 17
18 18
Output
YES
NO
YES
NO


-----Note-----

In the first example we have the list $\{4, 2, 2, 7\}$, and we have the target $k = 5$. One way to achieve it is the following: first we choose the third element, obtaining the list $\{2, 0, 5\}$. Next we choose the first element, obtaining the list $\{-2, 3\}$. Finally, we choose the first element, obtaining the list $\{5\}$.

Source: codeforces | Difficulty: EASY
Tags: Data structures

Amortized analysis

Mathematics

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def main():
	(N, K) = map(int, input().split())
	A = set(map(int, input().split()))
	for a in A:
		if K + a in A:
			return print('YES')
	print('NO')
T = int(input())
for _ in range(T):
	main()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	m = set(map(int, input().split()))
	for j in m:
		if j + k in m:
			print('YES')
			break
	else:
		print('NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = set(l)
	c = 0
	for j in m:
		if j + k in m:
			print('YES')
			c += 1
			break
	if c == 0:
		print('NO')


def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set(arr)
	for i in range(n):
		if arr[i] - k in s:
			print('YES')
			return
	print('NO')
tst = int(input())
for i in range(tst):
	solve()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	a = set(map(int, input().split(' ', n)))
	bol = 'NO'
	for x in a:
		if x - k in a:
			bol = 'YES'
			break
	print(bol)


import math as m
for i in range(int(input())):
	(a, b) = map(int, input().split())
	lis = list(map(int, input().split()))
	s = set(lis)
	for i in lis:
		if i + b in s:
			print('YES')
			break
	else:
		print('NO')


def solve():
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	for i in a:
		if k + i in a:
			print('YES')
			return
	print('NO')
for _ in range(int(input())):
	solve()


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = input().split(' ')
		k = int(k)
		arr = [int(c) for c in input().split(' ')]
		if k == 0:
			cnt = set()
			flag = True
			for num in arr:
				if num in cnt:
					print('YES')
					flag = False
			if flag:
				print('NO')
			continue
		brr = set(arr)
		flag = True
		for num in arr:
			if num - k in brr:
				print('YES')
				flag = False
				break
		if flag:
			print('NO')
main()


def subtract(a, k):
	for i in a:
		if i + k in a or i - k in a:
			return 1
	return 0
T = int(input())
for i in range(T):
	(n, k) = list(map(int, input().split()))
	a = set(map(int, input().split()))
	result = subtract(a, k)
	if result == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = set([*map(int, input().split())])
	for i in a:
		if i - k in a:
			print('YES')
			break
	else:
		print('NO')


from collections import defaultdict, deque
import sys
input = lambda : sys.stdin.readline().strip()
test_cases = int(input())
while test_cases > 0:
	test_cases -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = set(a)
	count = 'NO'
	for i in s:
		if k + i in s:
			count += 'YES'
			break
	print('YES' if 'YES' in count else 'NO')


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	se = set(l)
	flag = 0
	for i in se:
		if i - k in se:
			print('YES')
			flag = 1
			break
	if flag == 0:
		print('NO')


a = int(input())
for i in range(a):
	(b, c) = list(map(int, input().split()))
	d = set(map(int, input().split()))
	for i in d:
		if i + c in d:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = set(l)
	print('YES' if any((k + i in x for i in l)) else 'NO')


I = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = I()
	l = [*I()]
	x = set(l)
	print('YNEOS'[1 - any((k + i in x for i in l))::2])


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = set(map(int, input().split()))
	ans = 'NO'
	for i in l:
		if i + k in l:
			ans = 'YES'
			break
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = set(map(int, input().split()))
	count = 0
	for j in arr:
		if j + k in arr:
			print('YES')
			count = -1
			break
	if count == 0:
		print('NO')


import math
import collections
import itertools
import functools

def fun(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	s = set(arr)
	for i in range(n):
		if arr[i] - k in s:
			print('YES')
			return
	print('NO')
for tc in range(int(input())):
	fun(tc)


inputs = []
for _ in range(int(input())):
	inputs.append([[int(i) for i in input().split()], [int(i) for i in input().split()]])

def main(n, k, a):
	a = set(a)
	for i in a:
		if k + i in a:
			return 'YES'
	return 'NO'
for ((n, k), a) in inputs:
	print(main(n, k, a))


for _ in range(int(input())):
	res = False
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	li = set(l)
	for i in li:
		if i - k in li:
			res = True
			break
	if res:
		print('YES')
	else:
		print('NO')


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	flag = False
	s = set(a)
	for j in range(n):
		v = a[j] - k
		if v in s:
			flag = True
			break
	if flag == True:
		print('YES')
	else:
		print('NO')


def fun():
	(n, k) = list(map(int, input().split()))
	li = list(map(int, input().split()))
	s = set(li)
	for i in li:
		if i - k in s:
			print('YES')
			return
	print('NO')
t = int(input())
for _ in range(t):
	fun()


test_cases = int(input())
while test_cases > 0:
	test_cases -= 1
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	count = 'NO'
	for i in a:
		if k + i in a:
			count += 'YES'
			break
	print('YES' if 'YES' in count else 'NO')


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	A = set(map(int, input().split()))
	bool_ = False
	for a in A:
		if K + a in A:
			bool_ = True
	if bool_:
		print('YES')
	else:
		print('NO')


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	flag = 0
	for i in a:
		if i - k in d:
			flag = 1
	if flag == 1:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	f = 1
	res = {int(i): 1 for i in input().split()}
	for i in res.keys():
		val = i
		if res.get(val - k, 0):
			print('YES')
			f = 0
			break
	if f:
		print('NO')


x = int(input())
for i in range(x):
	(a, k) = map(int, input().split())
	c = set([int(i) for i in input().split()])
	t = 0
	for j in c:
		if j - k in c:
			t = 1
			print('YES')
			break
	if t == 0:
		print('NO')


test = int(input())
for t in range(test):
	(n, k) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	s = set(nums)
	ans = 'NO'
	for num in nums:
		if num + k in s:
			ans = 'YES'
			break
	print(ans)


from collections import Counter, defaultdict, deque, namedtuple
from functools import lru_cache
import re
from typing import List, Dict
import bisect as b
import heapq as h
import math as m

def inti():
	return int(input())

def ints():
	return [int(x) for x in input().split()]

def main_tc():
	(n, k) = ints()
	numbers = ints()
	s = set(numbers)
	for num in numbers:
		if num + k in s:
			print('YES')
			return
	print('NO')

def main():
	tc = inti()
	for _ in range(tc):
		main_tc()
main()


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = set(a)
	res = False
	for t in a:
		if k + t in s:
			res = True
			break
	if res:
		print('YES')
	else:
		print('NO')


import math, bisect, heapq, random, sys, itertools
input = sys.stdin.readline

def gprint(t, ans):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
ANS = []
for t in range(int(input())):
	(n, k) = ints()
	a = ints()
	a = set(a)
	x = 0
	for i in a:
		if k + i in a:
			x = 1
			break
	if x:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		d[i] = 1
	flag = 0
	for i in l:
		if k + i in d:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


def solution(n, k, nums):
	histo = {}
	for i in nums:
		if i not in histo:
			histo[i] = True
	for i in nums:
		if i - k in histo:
			print('YES')
			return
	print('NO')
	return
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	solution(n, k, nums)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	f = 0
	s = set(l)
	for i in s:
		if i - m in s:
			f = 1
			print('YES')
			break
	if f == 0:
		print('NO')


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a1 = a.copy()
	a1 = set(a1)
	flag = 0
	for i in range(n):
		if a[i] - k in a1:
			flag = 1
	if flag == 1:
		print('YES')
	else:
		print('NO')


def solve():
	(n, k) = [int(x) for x in input().split()]
	a = set([int(x) for x in input().split()])
	for num in a:
		if num - k in a:
			return 'YES'
	return 'NO'
for tc in range(int(input())):
	print(solve())


def solve():
	check = set(arr)
	for i in range(n):
		if arr[i] + k in check:
			return 'YES'
	return 'NO'
T = int(input())
for t in range(T):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


def f(S, k):
	for s in S:
		if s + k in S:
			return 'YES'
	return 'NO'
t = int(input())
for case in range(t):
	(n, k) = [int(num) for num in input().split()]
	S = set([int(num) for num in input().split()])
	print(f(S, k))


def Subtract(t):
	for i in range(t):
		N_and_K = list(map(int, input().split()))
		(n, k) = (N_and_K[0], N_and_K[1])
		INPUT = list(map(int, input().split()))
		Set = set(INPUT)
		p = 0
		for i in range(n):
			if INPUT[i] + k in Set:
				print('YES')
				p = 1
				break
		if p == 0:
			print('NO')
t = int(input())
Subtract(t)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set(arr)
	f = False
	for el in arr:
		if el - k in s:
			f = True
	if f:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	z = {}
	t = 0
	for i in a:
		z[i] = 1
	for i in a:
		if -(k - i) in z:
			t = 1
			break
	if t == 1:
		print('YES')
	else:
		print('NO')


def solve():
	(n, k) = input().split(' ')
	arr = set([int(i) for i in input().split(' ')])
	for elem in arr:
		if elem + int(k) in arr:
			print('YES')
			return
	print('NO')
t = int(input())
for i in range(t):
	solve()


def main():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr)
	ars = set()
	for z in arr:
		ars.add(k + z)
	arr = set(arr)
	for z in ars:
		if z in arr:
			return 'YES'
	return 'NO'
for _ in range(int(input())):
	print(main())


import sys
import math
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	for t in range(get_int()):
		(n, k) = get_ints_in_variables()
		arr = get_ints_in_list()
		mp = {}
		for i in range(0, n):
			if arr[i] not in mp:
				mp[arr[i]] = True
		flag = False
		for i in range(0, n):
			if arr[i] - k in mp:
				flag = True
				break
		if flag:
			print('YES')
		else:
			print('NO')
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = set(a)
	f = 0
	for i in b:
		if i + k in b:
			f = 1
			break
	if f:
		print('YES')
	else:
		print('NO')


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
import heapq
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 998244353

def func():
	(n, k) = mul()
	l = seq()
	l = set(l)
	ns = set()
	for i in l:
		ns.add(i - k)
	if l & ns:
		return 'YES'
	return 'NO'
t = inp()
for i in range(t):
	print(func())


from collections import defaultdict
from sys import stdin
input = stdin.readline

def get_string():
	return stdin.readline().strip()

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		nums = list(map(int, input().split()))
		d = defaultdict(int)
		for i in nums:
			d[i] += 1
		flag = 0
		for (x, y) in d.items():
			diff = x - k
			if diff == x and y > 1:
				print('YES')
				flag = 1
				break
			elif diff in d:
				print('YES')
				flag = 1
				break
		if flag == 0:
			print('NO')
main()


import sys
import math
data = sys.stdin.readlines()
numCases = int(data[0])
cases = []
for each in range(1, numCases + 1):
	line = data[each * 2 - 1].replace('\n', '').split(' ')
	k = int(line[1])
	line = data[each * 2].replace('\n', '')
	array = [int(x) for x in line.split(' ')]
	set_ = set(array)
	for i in set_:
		if i + k in set_:
			print('YES')
			break
	else:
		print('NO')


def sol(arr, n, k):
	di = {}
	for i in arr:
		di[i] = 1
	for i in arr:
		if di.get(i + k):
			return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().rstrip().split())
	arr = list(map(int, input().rstrip().split()))
	print(sol(arr, n, k))


def canget(nums, k):
	numset = set()
	for num in nums:
		if num + k in numset or num - k in numset:
			return True
		numset.add(num)
	return False
t = int(input())
for _ in range(t):
	(_, k) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	if canget(nums, k):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = [int(v) for v in input().split()]
	w = [int(v) for v in input().split()]
	q = set(w)
	for j in w:
		if j - k in q:
			print('YES')
			break
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	b = {}
	for i in a:
		b[i] = 1
	for i in a:
		if b.get(i - k):
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	s = set(a)
	key = 0
	for i in range(n):
		if a[i] - k in s:
			key = 1
			break
	if key == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	items = {x: 1 for x in a}
	possible = False
	for (i, item) in enumerate(a):
		if items.get(item - k):
			possible = True
	if possible:
		print('YES')
	else:
		print('NO')


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	st = set(arr)
	for i in st:
		if i + b in st:
			print('YES')
			break
	else:
		print('NO')


t = int(input())
while t:
	(n, k) = map(int, input().split())
	arr = [int(a) for a in input().split()]
	s = set(arr)
	for i in s:
		if i + k in s:
			print('YES')
			break
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = set([int(x) for x in input().split()])
	b = False
	for item in a:
		if item + k in a:
			b = True
			break
	if b:
		print('YES')
	else:
		print('NO')


def main():
	T = int(input())
	for k in range(T):
		(n, target) = list(map(int, input().split(' ')))
		array = list(map(int, input().split(' ')))
		freq = {}
		for i in range(n):
			if freq.get(array[i]) is None:
				freq[array[i]] = 1
			else:
				freq[array[i]] -= 1
		flag = False
		for x in array:
			if freq.get(x - target) is not None:
				flag = True
				break
		if flag:
			print('YES')
		else:
			print('NO')
main()


a = int(input())
for b in range(a):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	d = {}
	for element in lst:
		if element in d:
			continue
		d[element] = 0
	f = False
	for element in lst:
		if element + k in d:
			print('YES')
			f = True
			break
	if not f:
		print('NO')


for i in range(int(input())):
	(a, b) = map(int, input().strip().split())
	list1 = set(list(map(int, input().strip().split())))
	for i in list1:
		if i + b in list1 or i - b in list1:
			print('YES')
			break
	else:
		print('NO')


import sys
import math
for _ in range(int(sys.stdin.readline())):
	(n, k) = map(int, sys.stdin.readline().split())
	l = list(map(int, sys.stdin.readline().split()))
	d = {}
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = 1
	for x in d:
		if x - k in d:
			print('YES')
			break
	else:
		print('NO')


for T in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	d = set(A)
	valid = True
	for i in range(n):
		if A[i] + k in d:
			print('YES')
			valid = False
			break
	if valid:
		print('NO')


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mp = {}
	ans = 'NO'
	for ele in a:
		if ele in mp:
			mp[ele] += 1
		else:
			mp[ele] = 1
	for ele in a:
		temp = ele - k
		if temp in mp:
			ans = 'YES'
			break
	print(ans)


from collections import defaultdict as dd

def AbhiSolveKiya(n, k, a):
	d = dd(int)
	for i in a:
		d[i] = 1
	for i in a:
		if d[k + i] == 1:
			return 'YES'
	return 'NO'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(AbhiSolveKiya(n, k, a))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split(' ')))
	a = map(int, input().split(' '))
	vals = set()
	for item in a:
		if item + k in vals or item - k in vals:
			print('YES')
			break
		vals.add(item)
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	r = 'NO'
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	result = 0
	for i in l:
		if i - k in d:
			result = 1
	if result:
		r = 'YES'
	print(r)


from collections import deque, Counter
import math
T = int(input())
while T:
	T -= 1
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	count = Counter(A)
	flag = False
	for num in count:
		if num + k in count:
			flag = True
			break
	if flag:
		print('YES')
	else:
		print('NO')