You are given an array $A$ consisting of $N$ Integers which are initially all $0$. You are also given an array $B$ consisting of $N$ Integers. You have to tell whether you can make $A$ equal to $B$ or not by performing the following operation any number of times.

In one operation you can choose exactly $K$ distinct indices in the array A and increase the value at these indices by $1$.

------ Input: ------

First line will contain $T$, the number of testcases. Then the testcases follow. 
Each testcase contains two lines of input. 
First line contains two Integers $N$ and $K$.
Second line contains $N$ Integers denoting array $B$. 

------ Output: ------
For each testcase, output in a single line YES if $A$ can be converted to $B$, otherwise print NO.

------ Constraints  ------
$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$1 ≤ B[i] ≤ 10^{9}$
Sum of N over all Testcases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2   
5 3  
5 4 3 2 1  
3 2  
4 1 1
----- Sample Output 1 ------ 
YES  
NO

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
x = int(input())
for i in range(x):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	print('YES' if s % b == 0 and s / b >= max(l) else 'NO')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	print('YES' if s % k == 0 and s / k >= max(l) else 'NO')


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		s += i
	if s % k == 0 and s / k >= max(l):
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	maxi = max(a)
	if s % k == 0:
		r = s // k
		if r < maxi:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = get_ints()
	b = get_array()
	tot = sum(b)
	mx = max(b)
	if tot % k == 0 and mx <= tot // k:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	max = 0
	for el in l:
		s += el
		if el > max:
			max = el
	if s % k != 0:
		print('NO')
	else:
		s = s / k
		if max > s:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(s, m) = (sum(arr), max(arr))
	if s % k != 0:
		print('NO')
	elif m > s // k:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if sum(a) % k == 0 and max(a) * k <= sum(a):
		print('YES')
	else:
		print('NO')


try:
	from sys import stdin as si, stdout as so
	for _ in range(int(si.readline())):
		(n, k) = map(int, si.readline().split())
		b = list(map(int, si.readline().split()))
		m = max(b)
		s = sum(b)
		if s % k != 0:
			so.write('NO\n')
		elif m > s // k:
			so.write('NO\n')
		else:
			so.write('YES\n')
except:
	pass


t = int(input())
for h in range(t):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	s = sum(li)
	maxi = max(li)
	if s % k == 0:
		r = s // k
		if r < maxi:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


for u in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	m = max(l)
	if s % k != 0:
		print('NO')
	else:
		x = s / k
		if m > x:
			print('NO')
		else:
			print('YES')


for j in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	a = sum(x)
	b = max(x)
	if a % k == 0:
		c = a // k
		if c < b:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, m) = [int(n) for n in input('').split()]
	l = list(map(int, input().split()))
	sum = 0
	pol = 0
	for j in l:
		sum += j
		if pol < j:
			pol = j
	if sum % m != 0:
		print('NO')
	else:
		sum /= m
		if sum < pol:
			print('NO')
		else:
			print('YES')


t = int(input())
for i in range(t):
	(n, k) = [int(d) for d in input().split()]
	l = [int(f) for f in input().split()]
	if sum(l) % k != 0:
		print('NO')
	elif max(l) <= sum(l) // k:
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		if sum(arr) % k != 0:
			print('NO')
		elif max(arr) <= sum(arr) // k:
			print('YES')
		else:
			print('NO')
main()


def solve():
	(x, y) = map(int, input().split())
	s = list(map(int, input().split()))
	sm = sum(s)
	mx = max(s)
	if mx * y > sm or sm % y != 0:
		print('NO')
	else:
		print('YES')
for n in range(int(input())):
	solve()


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	s = sum(arr)
	if s % k == 0:
		if max(arr) > s // k:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	ans = max(arr)
	total = sum(arr)
	if total % k != 0:
		print('NO')
		continue
	req = total // k
	if ans > req:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	t -= 1
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	s = sum(arr)
	if s % k != 0 or max(arr) > s // k:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sumu = sum(l)
	if sumu % k == 0:
		flag = 0
		for i in l:
			if i > sumu // k:
				flag = 1
				break
		if flag:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	o = sum(a) - max(a) * p
	if o >= 0 and o % p == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(N, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	if s % k != 0:
		print('NO')
		continue
	if max(l) > s // k:
		print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	s = sum(x)
	maxo = max(x)
	if s % k != 0:
		print('NO')
	else:
		s = s / k
		if maxo > s:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	arr_B = [int(x) for x in input().split()]
	sums = sum(arr_B)
	maxs = max(arr_B)
	if sums % K != 0:
		ans = 'NO'
	elif sums // K < maxs:
		ans = 'NO'
	else:
		ans = 'YES'
	print(ans)


import math
t = int(input().strip())
for it in range(t):
	(n, k) = [int(i) for i in input().strip().split(' ')]
	arr = [int(i) for i in input().strip().split(' ')]
	sum = 0
	for i in arr:
		sum = sum + i
	if not sum % k == 0:
		print('NO')
		continue
	sum = sum / k
	val = True
	for i in arr:
		val = val and i <= sum
	if val:
		print('YES')
	else:
		print('NO')


def solve():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sum_ = sum(l)
	if sum_ % k != 0:
		print('NO')
		return
	if max(l) > sum_ // k:
		print('NO')
		return
	print('YES')
for _ in range(int(input())):
	solve()


tc = int(input())
for _ in range(tc):
	l1 = [int(i) for i in input().split()]
	(n, k) = (l1[0], l1[1])
	b = [int(i) for i in input().split()]
	m = max(b)
	s = sum(b)
	if s % k != 0 or m > s // k:
		print('NO')
	else:
		print('YES')


import sys
import math
read = lambda : list(map(int, sys.stdin.readline().strip().split()))
for _ in range(int(input())):
	(n, k) = read()
	b = read()
	if sum(b) % k == 0 and max(b) <= sum(b) // k:
		print('YES')
	else:
		print('NO')


t = int(input())
for z in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = list(map(int, input().split()))
	a = sorted(a)
	s = sum(a)
	l = len(a)
	last = a[l - 1]
	if s % k != 0 or last > int(s / k):
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	b = list(map(int, input().split()))
	d = max(b)
	c = sum(b)
	if c % k == 0:
		s = c // k
		if d > s:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	(N, K) = list(map(int, input().split()))
	B = list(map(int, input().split()))
	s = sum(B)
	a = max(B)
	if s % K == 0:
		s = s // K
		if a > s:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
S = lambda : input().strip()
mod = 1000000007
for i in range(I()):
	(n, m) = li()
	a = li()
	a.sort(reverse=True)
	s = sum(a)
	if s % m == 0 and a[0] * (m - 1) <= s - a[0]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	m = max(l)
	if s % k == 0:
		d = s // k
		if m > d:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = (int(x) for x in input().split())
	a = []
	a = [int(x) for x in input().split()]
	if k == 1:
		print('YES')
		continue
	s = sum(a)
	m = max(a)
	if s % k != 0 or m * k > s:
		print('NO')
		continue
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	if k == 1:
		print('YES')
	elif k == n:
		if len(set(li)) == 1:
			print('YES')
		else:
			print('NO')
	else:
		su = sum(li)
		if su % k != 0:
			print('NO')
		else:
			flag = 0
			ppp = su // k
			for i in li:
				if i > ppp:
					flag = 1
					break
			if flag == 0:
				print('YES')
			else:
				print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	i = 0
	nm = sum(ls)
	if nm % k == 0:
		if max(ls) <= nm // k:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	B = list(map(int, input().split()))
	print('YES') if sum(B) % K == 0 and max(B) <= sum(B) // K else print('NO')


def case():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	if s % k:
		print('NO')
		return
	if max(a) > s // k:
		print('NO')
		return
	print('YES')
for _ in range(int(input())):
	case()