Alice thinks of a non-decreasing sequence of non-negative integers and wants Bob to guess it by providing him the set of all its K-sums with repetitions. 

What is this? Let the sequence be {A[1], A[2], ..., A[N]} and K be some positive integer that both Alice and Bob know. Alice gives Bob the set of all possible values that can be genereated by this - A[i_{1}] + A[i_{2}] + ... + A[i_{K}], where 1 ≤ i_{1} ≤ i_{2} ≤ ... ≤ i_{K} ≤ N. She can provide the values generated in any order she wishes to. Bob's task is to restore the initial sequence.

Consider an example. Let N = 3 and K = 2. The sequence is {A[1], A[2], A[3]}. The sequence of its 2-sums with repetitions is {A[1] + A[1], A[1] + A[2], A[1] + A[3], A[2] + A[2], A[2] + A[3], A[3] + A[3]}. But its elements could be provided in any order. For example any permutation of {2, 3, 4, 4, 5, 6} corresponds to the sequence {1, 2, 3}.

Input Format

The first line of the input contains an integer T denoting the number of test cases. 

The description of T test cases follows. 

The first line of each test case contains two space separated integers N and K. 

The second line contains the sequence S_{i} of all K-sums with repetitions of the sequence Alice initially thought of.

Constraints

$1\leq T\leq10^5$  
$1\leq N\leq10^5$  
$1\leq K\leq10^9$  
$2\leq S_i\leq10^{18}$  

Note 

The total number of elements in any input sequence does not exceed 10^{5} 

Each element of each input sequence is non-negative integer not exceeding 10^{18}. 

Each input sequence is a correct sequence of all K-sums with repetitions of some non-decreasing sequence of non-negative integers.

Output Format

For each test case, output a single line containing the space separated list of elements of the non-decreasing sequence Alice thinks of. If there are several possible outputs you can output any of them.

Sample Input 0
3
1 3
3
2 2
12 34 56
3 2
2 3 4 4 5 6

Sample Output 0
1
6 28
1 2 3

Explanation 0

Sample case #00: When N = 1 and K = 3 the only K-sum is
S[1] = 3 * A[1]. Hence A[1] = S[1] / 3 = 3 / 3 = 1.

Sample case #01: Since 6 + 6 = 12, 6 + 28 = 34, 28 + 28 =
56, then Alice indeed could think of the sequence {6, 28}.

Sample case #02: It corresponds to the example in the problem
statement.

Difficulty: HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
from collections import Counter
import sys
sys.setrecursionlimit(10000)
T = int(input())
for case in range(T):
	(N, K) = map(int, input().split())
	S = list(sorted(map(int, input().split())))
	A = [0] * N
	used = Counter(S)
	i = 0
	for s in S:
		if used[s] == 0:
			continue
		A[i] = s - (K - 1) * A[0] if i != 0 else s // K

		def set_used(sum, idx, cnt):
			if cnt == K:
				used.subtract([sum])
				return
			set_used(sum + A[idx], idx, cnt + 1)
			if idx > 0:
				set_used(sum, idx - 1, cnt)
		set_used(A[i], i, 1)
		i += 1
		if i == N:
			break
	print(' '.join(map(str, A)))


from collections import OrderedDict

def blah(value, num, h, d, a):
	if value == 0:
		num += h * a[0]
	if h == 0 or value == 0:
		d[num] = d[num] - 1
		if d[num] == 0:
			del d[num]
		return
	for i in range(h + 1):
		blah(value - 1, num + i * a[value], h - i, d, a)
tests = int(input())
for test in range(tests):
	(n, k) = (int(x) for x in input().split())
	b = [int(x) for x in input().split()]
	a = [0 for x in range(n)]
	d = OrderedDict()
	for i in range(len(b)):
		if b[i] in d:
			d[b[i]] = d[b[i]] + 1
		else:
			d[b[i]] = 1
	for i in range(n):
		for value in d:
			break
		if i == 0:
			a[i] = int(value / k)
			d[value] = d[value] - 1
			if d[value] <= 0:
				del d[value]
		else:
			a[i] = int(value - a[0] * (k - 1))
			for j in range(1, k + 1):
				blah(i - 1, a[i] * j, k - j, d, a)
	print(*a, sep=' ')


t = int(input())
for tk in range(t):
	[n, k] = [int(x) for x in input().split()]
	ksums = [int(x) for x in input().split()]
	ksums.sort()
	seq = []
	seq.append(ksums.pop(0) // k)
	if n == 1:
		print(seq[0])
		continue
	partitions = []

	def addItem(listsofar, maxn):
		if len(listsofar) == k - 1:
			partitions[-1].append([x for x in listsofar])
			return
		minm = 0
		if len(listsofar) > 0:
			minm = listsofar[-1]
		for m in range(minm, maxn):
			listsofar.append(m)
			addItem(listsofar, maxn)
			listsofar.pop()
	for m in range(1, n + 1):
		partitions.append([])
		addItem([], m)
	for p in partitions:
		p.pop(0)
	valuestoskip = {}
	while True:
		nextvalue = ksums.pop(0)
		if valuestoskip.setdefault(nextvalue, 0) == 0:
			seq.append(nextvalue - seq[0] * (k - 1))
			if len(seq) == n:
				break
			for p in partitions[len(seq) - 1]:
				valuetoskip = sum([seq[x] for x in p]) + seq[-1]
				valuestoskip[valuetoskip] = valuestoskip.setdefault(valuetoskip, 0) + 1
		else:
			valuestoskip[nextvalue] -= 1
	print(*seq)


from collections import defaultdict

def get_sums(a, pos, k):
	if k == 0:
		yield 0
		return
	yield (a[pos - 1] * k)
	if pos > 1:
		for i in range(k):
			for s in get_sums(a, pos - 1, k - i):
				yield (s + a[pos - 1] * i)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	explained = defaultdict(int)
	A = []
	A.append(a[0] // k)
	explained[a[0]] = 1
	for x in a:
		if explained[x] == 0:
			A.append(x - A[0] * (k - 1))
			for s in get_sums(A, len(A), k - 1):
				explained[s + A[-1]] += 1
		explained[x] -= 1
	print(' '.join(map(str, sorted(A))))


import itertools as it
T = int(input().strip())
for Loopi in range(T):
	(N, k) = [int(m) for m in input().strip().split()]
	S = [int(m) for m in input().strip().split()]
	SCount = {}
	for i1 in S:
		if SCount.get(i1) == None:
			SCount[i1] = 1
		else:
			SCount[i1] += 1
	SUniq = sorted(SCount.keys())
	A1 = [int(SUniq[0] / k)]
	SCount[SUniq[0]] -= 1
	if SCount[SUniq[0]] == 0:
		del SUniq[0]
	while len(SUniq) > 0:
		A1.append(SUniq[0] - A1[0] * (k - 1))
		for i1 in it.combinations_with_replacement(A1, k - 1):
			STemp = sum(i1) + A1[-1]
			SCount[STemp] -= 1
		SUniqNew = []
		for i1 in SUniq:
			if SCount[i1] > 0:
				SUniqNew.append(i1)
		SUniq = SUniqNew
	Space = ''
	for i1 in A1:
		print(Space + str(i1), end='')
		Space = ' '
	print('')


from itertools import combinations_with_replacement
from collections import Counter

def solve(N, K, l):
	s = Counter(l)
	m = min(s) // K
	s[m * K] -= 1
	if s[m * K] == 0:
		del s[m * K]
	seq = [m]
	while len(seq) < N:
		x = min(s) - m * (K - 1)
		s[K * x] -= 1
		if s[K * x] == 0:
			del s[K * x]
		for j in range(1, K):
			for c in combinations_with_replacement(seq, j):
				y = x * (K - j) + sum(c)
				s[y] -= 1
				if s[y] == 0:
					del s[y]
		seq.append(x)
	return seq
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	l = list(map(int, input().split()))
	print(' '.join(map(str, solve(N, K, l))))


from heapq import *
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = list(map(int, input().split()))
	S = sorted(S)
	if K == 1:
		print(*S)
		continue
	a = [S[0] // K]
	h = [S[0]]

	def pushall(i, k, s):
		if i == 0:
			heappush(h, s + k * a[0])
			return
		for ki in range(k + 1):
			pushall(i - 1, k - ki, s + ki * a[i])
	for s in S:
		if len(h) and s == h[0]:
			heappop(h)
			continue
		e = s - a[0] * (K - 1)
		a.append(e)
		for ki in range(1, K + 1):
			pushall(len(a) - 2, K - ki, ki * e)
		assert h[0] == s
		heappop(h)
	print(*a)


from math import factorial as fact
from collections import deque, OrderedDict

class InputMap:

	def __init__(self, array):
		array.sort()
		d = OrderedDict()
		for val in array:
			if val not in d:
				d[val] = 0
			d[val] += 1
		self.data = d

	def deincrement(self, key):
		if key not in self.data:
			return
		self.data[key] -= 1
		if self.data[key] == 0:
			del self.data[key]

	def current_key(self):
		return next(iter(self.data))

def reconstruct(input_map, n, k):
	current = input_map.current_key()
	answer = [current // k]
	input_map.deincrement(current)

	def remove_sums(new, n, k):
		if n == 0 or k == 0:
			new += k * answer[0]
			input_map.deincrement(new)
			return
		for j in range(k + 1):
			next_new = new + j * answer[n]
			remove_sums(next_new, n - 1, k - j)
	for i in range(1, n):
		current = input_map.current_key()
		answer.append(current - answer[0] * (k - 1))
		for j in range(1, k + 1):
			next_value = answer[i] * j
			remove_sums(next_value, i - 1, k - j)
	return answer

def print_values(array):
	for result in array:
		if not result:
			print('')
		else:
			print(' '.join(result))
values = []
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	arr = [int(val) for val in input().split(' ')]
	values.append(map(str, reconstruct(InputMap(arr), n, k)))
print_values(values)


from collections import OrderedDict

class InputMap:

	def __init__(self, array):
		array.sort()
		d = OrderedDict()
		for val in array:
			if val not in d:
				d[val] = 0
			d[val] += 1
		self.data = d

	def deincrement(self, key):
		if key not in self.data:
			return
		self.data[key] -= 1
		if self.data[key] == 0:
			del self.data[key]

	def current_key(self):
		return next(iter(self.data))

def reconstruct(input_map, n, k):
	current = input_map.current_key()
	answer = [current // k]
	input_map.deincrement(current)

	def remove_sums(pos):

		def inner(partial_sum, pos, terms_remaining):
			if pos == 0 or terms_remaining == 0:
				partial_sum += terms_remaining * answer[0]
				input_map.deincrement(partial_sum)
				return
			for j in range(terms_remaining + 1):
				new_sum = partial_sum + j * answer[pos]
				inner(new_sum, pos - 1, terms_remaining - j)
		for j in range(1, k + 1):
			seed = answer[pos] * j
			inner(seed, pos - 1, k - j)
	for i in range(1, n):
		current = input_map.current_key()
		answer.append(current - answer[0] * (k - 1))
		remove_sums(i)
	return answer

def print_values(array):
	for result in array:
		if not result:
			print('')
		else:
			print(' '.join(result))
values = []
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	arr = [int(val) for val in input().split(' ')]
	values.append(map(str, reconstruct(InputMap(arr), n, k)))
print_values(values)


import sys

class SumConstructor:

	def __init__(self, k, s_0, in_list, a_0, in_floor):
		self.steps = [k - 1]
		self.values = [s_0]
		self.newSums = {s_0: 1}
		self.read = 0
		self.next = 1
		self.floor = s_0 - a_0
		self.input = in_list
		self.output = [a_0]

	def addSum(self, vsum):
		if self.newSums.setdefault(vsum, 0) == 0:
			self.newSums[vsum] += 1
		else:
			self.newSums[vsum] += 1

	def remSum(self, vsum):
		occ_nb = self.newSums.get(vsum, -1)
		if occ_nb == -1:
			return False
		elif occ_nb == 1:
			del self.newSums[vsum]
			return True
		else:
			self.newSums[vsum] -= 1
			return True

	def write(self, diff):
		i = 0
		wr_value = self.values[self.read] + diff
		while i <= self.steps[self.read]:
			self.steps.append(i)
			self.values.append(wr_value)
			self.addSum(wr_value)
			wr_value += diff
			self.next += 1
			i += 1
		self.read += 1

	def createSums(self, diff):
		self.newSums = dict()
		for index in range(self.read, self.next):
			self.write(diff)

	def clearList(self):
		i = 0
		while self.newSums != {}:
			if self.remSum(self.input[i]) == True:
				del self.input[i]
			else:
				i += 1

	def completeOut(self):
		prev = self.output[-1]
		new = self.input[0] - self.floor
		self.output.append(new)
		return new - prev

def solve(n, k, l):
	l = sorted(l)
	s_0 = l[0]
	a_0 = s_0 // k
	floor = s_0 - a_0
	constructor = SumConstructor(k, s_0, l, a_0, floor)
	for index in range(0, n - 1):
		constructor.clearList()
		delta = constructor.completeOut()
		constructor.createSums(delta)
	return constructor.output

def main():
	nb_case = int(input())
	for index in range(0, nb_case):
		(n, k) = map(int, input().split(' '))
		l = map(int, input().split(' '))
		sys.stdout.write(' '.join(map(str, solve(n, k, l))))
		if index != nb_case:
			sys.stdout.write('\n')
main()


from collections import Counter

def choose(n, k):
	r = 1
	for i in range(k):
		r = r * (n - i) // (i + 1)
	return r

def sums(a, k, plus=0):
	if k == 0:
		yield plus
	elif len(a) >= 1:
		for i in range(k + 1):
			yield from sums(a[1:], i, plus + a[0] * (k - i))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = sorted(map(int, input().split()))
	assert len(s) == choose(n - 1 + k, k)
	assert s[0] % k == 0
	a = [s[0] // k]
	c = Counter([s[0]])
	for v in s:
		if c[v] == 0:
			nexta = v - (k - 1) * a[0]
			for i in range(k):
				for s in sums(a, i, (k - i) * nexta):
					c[s] += 1
			assert c[v] >= 1
			a.append(nexta)
			if len(a) == n:
				break
		c[v] -= 1
	print(' '.join(map(str, a)))


import sys
from math import factorial
assert 10 ** 18 <= sys.maxsize
DEBUG = False

def eprint(*args, **kwargs):
	if DEBUG:
		print(*args, file=sys.stderr, **kwargs)

def binomial_coefficient(n, k):
	try:
		binom = factorial(n) // factorial(k) // factorial(n - k)
	except ValueError:
		binom = 0
	return binom

def multiset_coefficient(n, k):
	return binomial_coefficient(n + k - 1, k)

def get_known_sums_iterative(i, k, A):
	stack = []
	if i == 0:
		sums = [k * A[0]]
	else:
		sums = []
		for j in reversed(range(1, k + 1)):
			stack.append((i - 1, k - j, j * A[i]))
	while stack:
		(i_, k_, sum_) = stack.pop()
		if i_ == 0:
			sums.append(sum_ + k_ * A[0])
		else:
			for j in reversed(range(k_ + 1)):
				stack.append((i_ - 1, k_ - j, sum_ + j * A[i_]))
	return sums

class MultiSet(object):

	def __init__(self, items=None):
		self.elements = {}
		if items:
			for item in items:
				self.add(item)

	def __str__(self):
		return str(self.elements)

	def __iter__(self):
		return self.elements.__iter__()

	def add(self, item):
		try:
			self.elements[item] += 1
		except KeyError:
			self.elements[item] = 1

	def remove(self, item):
		count = self.elements.pop(item)
		if count > 1:
			self.elements[item] = count - 1
t = int(input().strip())
for i in range(t):
	eprint()
	(n, k) = [int(x) for x in input().strip().split(' ')]
	S = sorted([int(s) for s in input().strip().split(' ')])
	m = multiset_coefficient(n, k)
	assert len(S) == m
	if k == 1:
		A = S
		print(' '.join([str(a) for a in A]))
		continue
	S = MultiSet(S)
	A = [-1] * n
	for j in range(n):
		if j == 0:
			A[j] = min(S) // k
		else:
			A[j] = min(S) - A[0] * (k - 1)
		for s in get_known_sums_iterative(j, k, A):
			S.remove(s)
	print(' '.join([str(a) for a in A]))


from collections import Counter

def ks(A, k, C, o):
	if k == 0:
		C[o] -= 1
		return
	for (i, a) in enumerate(A):
		ks(A[i:], k - 1, C, o + a)

def solve(N, K, ar):
	C = Counter(ar)
	keys = sorted(C)
	A = [keys[0] // K]
	C[keys[0]] -= 1
	j = 0
	for i in range(1, N):
		while C[keys[j]] == 0:
			j += 1
		A.append(keys[j] - (K - 1) * A[0])
		ks(A, K - 1, C, A[-1])
	return ' '.join((str(x) for x in A))
for _ in range(int(input().strip())):
	((N, K), ar) = ([int(x) for x in input().split()], [int(x) for x in input().split()])
	print(solve(N, K, ar))


from collections import OrderedDict, Counter
from itertools import combinations_with_replacement as cwrs

class OrderedCounter(Counter, OrderedDict):
	pass

def solution(n, k, k_sums):
	if k == 1:
		return k_sums
	if n == 1:
		return [k_sums[0] // k]
	arr = []
	k_sums_map = OrderedCounter(k_sums)
	tot = R(n, k)
	for i in range(n):
		k_sum = next(iter(k_sums_map.keys()))
		if i == 0:
			arr.append(k_sum // k)
		else:
			arr_i = k_sum - arr[0] * (k - 1)
			arr.append(arr_i)
		clean_up(k_sums_map, arr, k)
	return arr

def clean_up(k_sums_map, arr, k):
	a_last = arr[-1]
	for cnt in range(1, k + 1):
		for combi in cwrs(arr[:-1], k - cnt):
			k_sum = sum(combi) + a_last * cnt
			k_sums_map[k_sum] -= 1
			if k_sums_map[k_sum] == 0:
				k_sums_map.pop(k_sum)

def R(n, k):
	if n == 0:
		return 0
	return C(n + k - 1, k)

def C(n, k):
	if n - k > k:
		return C(n, n - k)
	res = 1
	for i in range(k):
		res *= n - i
		res //= i + 1
	return res

def main():
	for tc in range(int(input())):
		(n, k) = map(int, input().strip().split())
		k_sums = list(map(int, input().strip().split()))
		print(*solution(n, k, k_sums))
main()


from collections import Counter

def solve(k, s):
	s = sorted(s)
	if k == 1:
		return s
	dp = [[] for _ in range(k)]
	skip = Counter()
	i = 0
	while i < len(s):
		if skip[s[i]]:
			skip[s[i]] -= 1
			i += 1
			continue
		if i == 0:
			num = s[i] // k
		else:
			num = s[i] - dp[-2][0]
		dp[0].append(num)
		for j in range(1, k):
			skip.update((num + x for x in dp[j - 1]))
			dp[j].extend((num + x for x in dp[j - 1]))
	return dp[0]
for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	s = (int(x) for x in input().split())
	print(' '.join((str(x) for x in solve(k, s))))


def partial_sums(K, start, A):
	if start == len(A) - 1:
		yield (K * A[-1])
	else:
		for k in range(K):
			p = k * A[start]
			for s in partial_sums(K - k, start + 1, A):
				yield (p + s)
		yield (K * A[start])
for case in range(int(input().strip())):
	(N, K) = input().split()
	(N, K) = (int(N), int(K))
	Ksum = list(map(int, input().split()))
	Ksum.sort()
	if N == 1:
		print(Ksum[0] // K)
		continue
	if N % 2 == 0:
		Nmin = Nmax = N // 2
	else:
		Nmin = N // 2 + 1
		Nmax = N // 2
	Amin = [Ksum.pop(0) // K]
	for i in range(1, Nmin - 1):
		Amin.append(Ksum[0] - (K - 1) * Amin[0])
		for s in partial_sums(K - 1, 0, Amin):
			Ksum.remove(Amin[-1] + s)
	if Nmin > 1:
		Amin.append(Ksum[0] - (K - 1) * Amin[0])
	Ksum.reverse()
	Amax = [Ksum.pop(0) // K]
	for i in range(1, Nmax - 1):
		Amax.append(Ksum[0] - (K - 1) * Amax[0])
		for s in partial_sums(K - 1, 0, Amax):
			Ksum.remove(Amax[-1] + s)
	if Nmax > 1:
		Amax.append(Ksum[0] - (K - 1) * Amax[0])
	Amin.extend(reversed(Amax))
	print(' '.join(map(str, Amin)))


def allcomb(seq, k):
	if k == 0:
		return [0]
	lst = list()
	seqbis = list(seq)
	for a in seq:
		for b in allcomb(seqbis, k - 1):
			lst.append(a + b)
		seqbis.remove(a)
	return lst

def addSum(already, seq, nxt, k):
	for p in range(1, k + 1):
		for l in allcomb(seq, k - p):
			already.append(l + nxt * p)

def getSequence(n, k, ksum):
	seq = list()
	ksum = sorted(ksum)
	seq.append(int(ksum[0] / k))
	already = list()
	offset = 0
	for i in range(1, n):
		while ksum[i + offset] in already:
			already.remove(ksum[i + offset])
			offset += 1
		nxt = ksum[i + offset] - seq[0] * (k - 1)
		addSum(already, seq, nxt, k)
		seq.append(nxt)
		already.remove(ksum[i + offset])
	return seq
t = int(input())
for case in range(t):
	dim = [int(x) for x in input().split(' ')]
	n = dim[0]
	k = dim[1]
	ksum = [int(x) for x in input().split(' ')]
	res = getSequence(n, k, ksum)
	print(' '.join([str(x) for x in res]))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	s = [int(x) for x in input().split(' ')]
	s.sort()
	a = [s[0] // k]
	sac = [[a[0] * i] for i in range(k + 1)]
	p = 0
	while len(a) < n:
		while p < len(sac[k]) and s[p] == sac[k][p]:
			p += 1
		ai = s[p] - (k - 1) * a[0]
		a.append(ai)
		if len(a) == n:
			break
		for i in range(k, 0, -1):
			for j in range(i):
				sac[i].extend(((i - j) * ai + sacj for sacj in sac[j]))
		sac[k].sort()
	print(' '.join((str(ai) for ai in a)))


from itertools import combinations_with_replacement
from collections import deque

def combinations(collection, r):
	if len(collection) == 1 or r == 1:
		yield ((collection[-1],) * r)
	else:
		for c in combinations_with_replacement(collection, r - 1):
			yield (c + (collection[-1],))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	k_sums = deque(map(int, input().split()))
	remove = {}
	b = (k - 1) * (k_sums[0] // k)
	arr = []
	for _ in range(n):
		arr.append(k_sums[0] - b)
		for c in combinations(arr, k):
			r = sum(c)
			remove[r] = remove.get(r, 0) + 1
		while k_sums and remove.get(k_sums[0], 0) > 0:
			remove[k_sums.popleft()] -= 1
	print(' '.join(map(str, arr)))


import sys

def combinations_with_replacement(aa, k):
	if aa and k:
		sm = aa[0] * k
		yield ((aa[0],) * k, sm)
		for i in range(k - 1, 0, -1):
			sm -= aa[0]
			for (t, subsum) in combinations_with_replacement(aa[1:], k - i):
				yield ((aa[0],) * i + t, sm + subsum)
		yield from combinations_with_replacement(aa[1:], k)

def solve(n, k, aa):
	if k == 1:
		return aa
	cache = dict()
	for a in aa:
		if a in cache:
			cache[a] += 1
		else:
			cache[a] = 1
	mm = []
	while len(mm) != n:
		if len(mm) == 0:
			m = min(cache) // k
		else:
			m = min(cache) - mm[0] * (k - 1)
		mm.append(m)
		for (t, sm) in combinations_with_replacement(mm, k - 1):
			sm += m
			cache[sm] -= 1
			if cache[sm] == 0:
				cache.pop(sm)
	return mm
import resource
resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	aa = list(map(int, input().split()))
	mm = solve(n, k, aa)
	for m in mm:
		print(m, end=' ')
	print()


import sys
sys.setrecursionlimit(2000)
num_cases = int(input().strip())
test_cases = []
while num_cases > 0:
	(n, k) = list(map(int, input().strip().split(' ')))
	ksum = list(map(int, input().strip().split(' ')))
	test_cases.append((n, k, ksum))
	num_cases -= 1

class Solution:

	def solver(self, n, k, ksum):
		self.res = []
		self.perm_dic = {}
		self.index_dic = {}
		self.removed = set()
		ksum.sort()
		for i in range(len(ksum)):
			if ksum[i] in self.index_dic:
				self.index_dic[ksum[i]].append(i)
			else:
				self.index_dic[ksum[i]] = [i]
		self.res = [ksum[-1] // k]
		i = len(ksum) - 1
		self.index_dic[ksum[i]].pop()
		if self.index_dic[ksum[i]] == []:
			del self.index_dic[ksum[i]]
		self.removed.add(i)
		index = i - 1
		self.helper(n, k, ksum, index)
		return self.res

	def helper(self, n, k, ksum, index):
		if index < 0:
			return
		if ksum == []:
			return
		self.res_temp = [ksum[index] - self.res[-1] * (k - 1)]
		self.res = self.res_temp + self.res
		self.removed.add(index)
		if len(self.res) == n:
			return
		res_per = self.permutation(self.res, k)
		res_pre = self.permutation(self.res[1:], k)
		res_diff = res_per[:-len(res_pre)]
		res_per_sum = [sum(per) for per in res_diff]
		for s in res_per_sum:
			i = self.index_dic[s].pop()
			if len(self.index_dic[s]) == 0:
				del self.index_dic[s]
			self.removed.add(i)
		while index in self.removed:
			index -= 1
		self.helper(n, k, ksum, index)

	def permutation(self, l, n):
		if (tuple(l), n) in self.perm_dic:
			return self.perm_dic[tuple(l), n]
		if l == []:
			return []
		if n == 0:
			return [[]]
		self.perm_dic[tuple(l), n] = [[l[0]] + p for p in self.permutation(l, n - 1)] + self.permutation(l[1:], n)
		return self.perm_dic[tuple(l), n]
sol = Solution()
for cases in test_cases:
	(n, k, ksum) = cases
	res = sol.solver(n, k, ksum)
	print(' '.join(list(map(str, res))))


def insertion_sort(a):
	for i in range(0, len(a) - 1):
		j = i
		while a[j] > a[j + 1] and j >= 0:
			temp = a[j]
			a[j] = a[j + 1]
			a[j + 1] = temp
			j -= 1
	return a

def merge_lists(a, b):
	final_list = []
	pos_a = 0
	pos_b = 0
	while pos_a + pos_b < len(a) + len(b):
		if pos_a < len(a) and pos_b < len(b) and (a[pos_a] <= b[pos_b]):
			final_list.append(a[pos_a])
			pos_a += 1
		elif pos_a < len(a) and pos_b < len(b) and (a[pos_a] > b[pos_b]):
			final_list.append(b[pos_b])
			pos_b += 1
		elif pos_a == len(a) and pos_b < len(b):
			final_list.append(b[pos_b])
			pos_b += 1
		elif pos_a < len(a) and pos_b == len(b):
			final_list.append(a[pos_a])
			pos_a += 1
		else:
			print('error')
	return final_list

def merge_sort(a):
	if len(a) < 10:
		return insertion_sort(a)
	else:
		return merge_lists(merge_sort(a[0:len(a) // 2]), merge_sort(a[len(a) // 2:len(a)]))

def generate_all_k_sums(L, K, current_sum=0, start_index=0):
	ret_list = []
	if K == 0 and start_index < len(L):
		return [current_sum]
	elif start_index == len(L) - 1 and K >= 0:
		return [current_sum + K * L[start_index]]
	else:
		for i in range(0, K + 1):
			if K - i >= 0:
				ret_list += generate_all_k_sums(L, K - i, current_sum + i * L[start_index], start_index + 1)
	return ret_list

def reverse_k_sums(A, n, k):
	current_list = [A[0] // k]
	while len(current_list) < n:
		k_sums = merge_sort(generate_all_k_sums(current_list, k))
		i = 0
		found = False
		while i < len(k_sums) and (not found):
			if A[i] != k_sums[i]:
				current_list.append(A[i] - current_list[0] * (k - 1))
				found = True
			i += 1
		if not found and i == len(k_sums):
			current_list.append(A[i] - current_list[0] * (k - 1))
	return current_list

def repksum():
	test_cases = int(input())
	for q in range(0, test_cases):
		(N, K) = [int(a) for a in input().split()]
		rks = merge_sort([int(a) for a in input().split()])
		if K > 1:
			original_list = [str(a) for a in reverse_k_sums(rks, N, K)]
		elif K == 1:
			original_list = [str(a) for a in rks]
		print(' '.join([str(a) for a in original_list]))
repksum()


import math

def numcom(n, k):
	return math.factorial(n + k - 1) // (math.factorial(k) * math.factorial(n - 1))

def indirec(num, rep):
	if rep == 1:
		return [[i] for i in list(range(num))]
	ant = indirec(num, rep - 1)
	res = []
	for x in ant:
		res += [x + [i + x[-1]] for i in list(range(num - x[-1]))]
	return res

def dotpro(x, indx):
	res = [[x[i] for i in y] for y in indx]
	if type(res[0][0]) == int:
		return [sum(x) for x in res]
	return [''.join(x) for x in res]

def indclas(num, indx):
	res = [[] for i in range(num)]
	for y in indx:
		mx = max(y)
		res[mx] += [y]
	return res

def gensecnbajo(n, k, sumas):
	secmax = []
	if n >= 1:
		raiz = sumas[0] // k
		sec = [raiz]
	if n >= 2:
		sec += [sumas[1] - (k - 1) * raiz]
	if n > 2:
		raizmax = sumas[-1] // k
		secmax += [raizmax]
	if n > 3:
		secmax += [sumas[-2] - (k - 1) * raizmax]
	if n == 5:
		secmax += [sum(sumas) // (numcom(n, k) * k // n) - sum(sec) - sum(secmax)]
	sec += secmax
	sec.sort()
	return sec

def generasec(n, k, sumas):
	indices = indclas(n, indirec(n, k))
	secmax = []
	if n > 2:
		raizmax = sumas[-1] // k
		secmax += [raizmax]
	if n > 3:
		secmax += [sumas[-2] - (k - 1) * raizmax]
	for i in range(n):
		if i == 0:
			raiz = sumas[0] // k
			sec = [raiz]
		else:
			sec += [sumas[0] - (k - 1) * raiz]
		if n <= len(sec) + len(secmax):
			sec += [x for x in reversed(secmax)]
			break
		spar = dotpro(sec, indices[i])
		for y in spar:
			sumas.remove(y)
	sec.sort()
	return sec
casos = int(input())
for caso in range(casos):
	(n, k) = map(int, input().strip().split(' '))
	sumas = list(map(int, input().strip().split(' ')))
	sumas.sort()
	if k == 1:
		sec = sumas
	elif n <= 5:
		sec = gensecnbajo(n, k, sumas)
	else:
		sec = generasec(n, k, sumas)
	print(' '.join(map(str, sec)))


from itertools import combinations_with_replacement

def print_results(res_set):
	output = ' '.join([str(e) for e in res_set])
	print(output)

def is_set_for_index(aSet, index):
	for e in aSet:
		if e != index:
			return False
	return True
T = int(input())
for num_tests in range(T):
	input_line = input()
	(n, k) = [int(x) for x in input_line.strip().split(' ')]
	input_line = input()
	ksums = [int(x.strip()) for x in input_line.strip().split(' ') if x != '']
	res_set = []
	if k == 1:
		res_set = ksums
		print_results(res_set)
		continue
	if n == 1:
		res_set.append(int(ksums[0] / k))
		print_results(res_set)
		continue
	xList = [x for x in range(n)]
	seq_set = list(combinations_with_replacement(xList, k))
	curr_index = len(res_set)
	curr_set = seq_set[0]
	if is_set_for_index(curr_set, curr_index):
		res_set.append(ksums[0] // k)
		ksums.remove(ksums[0])
		seq_set.remove(curr_set)
	while n - len(res_set) > 0:
		curr_index = len(res_set)
		curr_set = seq_set[0]
		if sum(curr_set) == curr_index:
			curr_sum = ksums[0]
			curr_val = curr_sum - res_set[0] * (k - 1)
			res_set.append(curr_val)
			if n - len(res_set) == 1:
				res_set.append(ksums[-1] // k)
				continue
			for (i, t) in enumerate(seq_set):
				sums = 0
				if t[-1] <= curr_index:
					for e in t:
						sums += res_set[e]
					ksums.remove(sums)
					seq_set.pop(i)
	print_results(res_set)


inf = 10 ^ 18 + 1000

def merge(a, b):
	if len(a) == 0:
		return b[:]
	if len(b) == 0:
		return a[:]
	tmp = []
	i = 0
	j = 0
	while i < len(a) or j < len(b):
		if i < len(a):
			ai = a[i]
		else:
			ai = inf
		if j < len(b):
			bj = b[j]
		else:
			bj = inf
		if ai < bj:
			tmp.append(ai)
			i += 1
		else:
			tmp.append(bj)
			j += 1
	return tmp
q = int(input())
for ii in range(q):
	(n, K) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	if n == 1:
		print(a[0] // K)
		continue
	if n == 2:
		print(a[0] // K, a[len(a) - 1] // K)
		continue
	if n == 3:
		print(a[0] // K, a[1] - a[0] // K * (K - 1), a[len(a) - 1] // K)
		continue
	if n == 4:
		ans0 = a[0] // K
		ans1 = a[1] - ans0 * (K - 1)
		ans3 = a[len(a) - 1] // K
		ans2 = a[len(a) - 2] - (K - 1) * ans3
		print(ans0, ans1, ans2, ans3)
		continue
	ans = [a[0] // K]
	sums = []
	for k in range(K + 1):
		sums.append([k * ans[0]])
	for m in range(1, n):
		i = 0
		while i < len(sums[K]) and a[i] == sums[K][i]:
			i += 1
		ans.append(a[i] - (K - 1) * ans[0])
		new_sums = []
		new_sums.append([0])
		for k in range(1, K + 1):
			tmp_sums = sums[:k + 1]
			for l in range(1, k + 1):
				tmp_sums[k - l] = [x + y for (x, y) in zip(sums[k - l], [ans[m] * l] * len(sums[k - l]))]
			tmp = []
			for l in range(0, k + 1):
				tmp.extend(tmp_sums[l])
			new_sums.append(sorted(tmp))
		sums = new_sums[:]
	print(*ans, sep=' ')


cache = dict()

def permutation(data, k):
	key = tuple([k] + data)
	if key in cache:
		return cache[key]
	ret = [data[-1] * k]
	if len(data) == 1:
		return ret
	for i in range(k):
		for x in permutation(data[:-1], k - i):
			ret.append(data[-1] * i + x)
	cache[key] = sorted(ret)
	return cache[key]

def solve(n, k, sums):
	if n == 0:
		return []
	x = int(sums[0] / k)
	known = [x]
	sums.remove(x * k)
	sums = sorted(sums)
	while True:
		if len(sums) == 0:
			break
		tmp = x * (k - 1)
		y = sums[0] - tmp
		known.append(y)
		p = permutation(known, k - 1)
		i = 0
		for t in p:
			while True:
				if sums[i] == t + y:
					del sums[i]
					break
				i += 1
	return known
_t = int(input().strip())
for _ in range(_t):
	(_n, _k) = list(map(int, input().strip().split(' ')))
	_data = list(map(int, input().strip().split(' ')))
	print(' '.join([str(x) for x in solve(_n, _k, _data)]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


import sys
sys.setrecursionlimit(5000)
tests = int(input())

def generateKsum(seq, k, prevInd):
	if k == 1:
		return seq[prevInd:]
	result = []
	for i in range(prevInd, len(seq)):
		elem = seq[i]
		for sums in generateKsum(seq, k - 1, i):
			result.append(elem + sums)
	return result
for test in range(tests):
	(n, k) = [int(s) for s in input().split()]
	seq = [int(s) for s in input().split()]
	seq.sort()
	delete = {}
	found = [seq[0] // k]
	for (i, val) in enumerate(seq[1:]):
		if val in delete and delete[val] > 0:
			delete[val] -= 1
		else:
			found.append(val - (k - 1) * found[0])
			if len(found) == n:
				break
			for j in generateKsum(found, k, 0):
				delete[j] = delete.get(j, 0) + 1
			for j in generateKsum(found[:-1], k, 0):
				delete[j] -= 1
			for i in range(0, len(found) - 1):
				rem = found[i] + (k - 1) * found[0]
				delete[rem] += 1
			for i in range(0, len(found)):
				rem = found[i] + (k - 1) * found[0]
				delete[rem] -= 1
	print(' '.join([str(i) for i in found]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(v, val):
	v[val] -= 1
	if v[val] == 0:
		del v[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == k:
		decrement(v, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + a[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = sorted(list(map(int, input().split())))
	v = OrderedDict()
	for i in s:
		if i not in v:
			v[i] = 0
		v[i] += 1
	a = [s[0] // k] + [0] * (n - 1)
	decrement(v, s[0])
	for i in range(1, n):
		a[i] = list(v.keys())[0] - (k - 1) * a[0]
		if i < n - 1:
			del_rec(0, i, 1, a[i])
	print(' '.join([str(x) for x in a]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = map(int, input().strip().split())
	S = sorted(map(int, input().strip().split()))
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrementnode(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_recurrence(current_i, max_i, count, current_sum):
	if count == K:
		decrementnode(V, current_sum)
	else:
		del_recurrence(current_i, max_i, count + 1, current_sum + A[current_i])
		if current_i < max_i:
			del_recurrence(current_i + 1, max_i, count, current_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrementnode(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_recurrence(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = []
	used = {}
	for i in a:
		if not values:
			values.append(i // k)
			continue
		elif used.setdefault(i, 0) > 0:
			used[i] -= 1
		else:
			used[i] -= 1
			new_num = i - values[0] * (k - 1)
			for j in range(k):
				for u in map(lambda x: (k - j) * new_num + sum(x), cwr(values, j)):
					used[u] = used.get(u, 0) + 1
			values.append(new_num)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_recurrence(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_recurrence(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_recurrence(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_recurrence(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


import itertools as it
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ewan = sorted(map(int, input().split()))
	ans = [ewan[0] // k]
	vals = {}
	for x in ewan[1:]:
		if vals.setdefault(x, 0) > 0:
			vals[x] -= 1
		else:
			vals[x] -= 1
			new = x - ans[0] * (k - 1)
			for y in range(k):
				for z in map(lambda idk: (k - y) * new + sum(idk), it.combinations_with_replacement(ans, y)):
					vals[z] = vals.get(z, 0) + 1
			ans.append(new)
	print(' '.join(map(str, ans)))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(v, val):
	v[val] -= 1
	if v[val] == 0:
		del v[val]

def del_rec(cur, ma, c, su):
	if c == K:
		decrement(V, su)
	else:
		del_rec(cur, ma, c + 1, su + A[cur])
		if cur < ma:
			del_rec(cur + 1, ma, c, su)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


def comb(n, k):
	S = 1
	for i in range(k):
		S *= n - i
		S //= i + 1
	return S

def Ksums(w, K):
	if K == 1:
		return w
	elif len(w) == 1:
		return [(K * w[0][0], comb(K + w[0][1] - 1, w[0][1] - 1))]
	elif len(w) == 2:
		return [(j * w[0][0] + (K - j) * w[1][0], comb(j + w[0][1] - 1, w[0][1] - 1) * comb(K - j + w[1][1] - 1, w[1][1] - 1)) for j in range(K + 1)]
	else:
		W = dict()
		for j in range(K + 1):
			L = Ksums(w[:-1], K - j)
			for x in L:
				if x[0] + j * w[-1][0] in W:
					W[x[0] + j * w[-1][0]] += comb(j + w[-1][1] - 1, w[-1][1] - 1) * x[1]
				else:
					W[x[0] + j * w[-1][0]] = comb(j + w[-1][1] - 1, w[-1][1] - 1) * x[1]
		return list(W.items())

def solve(N, K, l):
	w = dict()
	i = 0
	x = l[0]
	w[x] = 0
	L = [x // K]
	S = {x // K: 1}
	while len(L) < N:
		i += 1
		x = l[i]
		if not x in w or w[x] == 0:
			y = x - (K - 1) * L[0]
			L.append(y)
			if y in S:
				for t in Ksums(list(S.items()), K):
					w[t[0]] -= t[1]
				S[y] += 1
				for t in Ksums(list(S.items()), K):
					w[t[0]] += t[1]
			else:
				for t in Ksums(list(S.items()), K):
					w[t[0]] -= t[1]
				S[y] = 1
				for z in Ksums(list(S.items()), K):
					if z[0] in w:
						w[z[0]] += z[1]
					else:
						w[z[0]] = z[1]
		w[x] -= 1
	return L
t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	l = map(int, input().split())
	l = sorted(l)
	print(*solve(N, K, l), sep=' ')


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


import sys
import itertools

def combinations(factors, k):
	return itertools.combinations_with_replacement(factors, k)

def cartesian_factors(seq, n, k):

	def _backsolve(seq, n, k, factors=[]):
		if len(seq) == 0:
			return factors
		if len(factors) == n:
			return factors
		a_0 = factors[0]
		s_n = seq[0]
		a_n = s_n - (k - 1) * a_0
		coefs = combinations(factors + [a_n], k - 1)
		for coef in coefs:
			seq.remove(sum(coef) + a_n)
		return _backsolve(seq, n, k, factors + [a_n])
	a_0 = seq[0] // k
	factors = [a_0]
	seq = seq[1:]
	return _backsolve(seq, n, k, factors)

def k_sums(seq, n, k):
	a = sorted(list(map(int, seq)))
	cwr = itertools.combinations_with_replacement
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	return values

def print_array(arr):
	items = [str(item) for item in arr]
	print(' '.join(items))

def print_solve(seq, n, k):
	print_array(k_sums(seq, n, k))
n_test_cases = input()
for _ in range(int(n_test_cases)):
	line_value = input().strip()
	(_n, _k) = line_value.split(' ')
	n = int(_n)
	k = int(_k)
	k_sum = [int(item) for item in input().strip().split(' ')]
	print_solve(k_sum, n, k)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from collections import OrderedDict

def decrement(V, val):
	V[val] -= 1
	if V[val] == 0:
		del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum):
	if cnt == K:
		decrement(V, cur_sum)
	else:
		del_rec(cur_i, max_i, cnt + 1, cur_sum + A[cur_i])
		if cur_i < max_i:
			del_rec(cur_i + 1, max_i, cnt, cur_sum)
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()]
	S = sorted([int(x) for x in input().strip().split()])
	V = OrderedDict()
	for x in S:
		if x not in V:
			V[x] = 1
		else:
			V[x] += 1
	A = [S[0] // K] + [0] * (N - 1)
	decrement(V, S[0])
	for n in range(1, N):
		A[n] = list(V.keys())[0] - (K - 1) * A[0]
		if n < N - 1:
			del_rec(0, n, 1, A[n])
	print(' '.join([str(x) for x in A]))


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as CR
from collections import defaultdict
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = list(map(int, input().split()))
	A = [S[0] // K]
	PendingSums = defaultdict(int)
	i = 1
	for _ in range(N - 1):
		while S[i] in PendingSums:
			if PendingSums[S[i]] == 1:
				del PendingSums[S[i]]
			else:
				PendingSums[S[i]] -= 1
			i += 1
		a = S[i] - (K - 1) * A[0]
		for k in range(K):
			for C in CR(A, k):
				s = sum(C) + (K - k) * a
				PendingSums[s] += 1
		A.append(a)
	print(*A)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	a = sorted(list(map(int, input().rstrip().split())))
	values = [a[0] // k]
	combinations = {}
	for i in a[1:]:
		if combinations.setdefault(i, 0) > 0:
			combinations[i] -= 1
		else:
			combinations[i] -= 1
			new_val = i - values[0] * (k - 1)
			for j in range(k):
				for new_comb in map(lambda x: (k - j) * new_val + sum(x), cwr(values, j)):
					combinations[new_comb] = combinations.get(new_comb, 0) + 1
			values.append(new_val)
	print(*values)


from itertools import combinations_with_replacement as cwr
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	L = sorted(map(int, input().split()))
	(R, D) = ([L[0] // K], {})
	for i in L[1:]:
		if D.setdefault(i, 0) > 0:
			D[i] -= 1
		else:
			D[i] -= 1
			V = i - R[0] * (K - 1)
			for j in range(K):
				for C in map(lambda x: (K - j) * V + sum(x), cwr(R, j)):
					D[C] = D.get(C, 0) + 1
			R.append(V)
	print(*R)