Read problems statements in Mandarin Chinese  and Russian. 

Chef Anup is making dishes. Each dish consists of N ingredients, and quantity of each ingredient is an integer between 1 and K inclusive.
Relative quality of 2 dishes is determined by their lexicographic order. Dish A is of lower quality than dish B if there is a position i (1≤i≤N) such that A_{j} = B_{j} for all j < i and A_{i} < B_{i}. 
E.g., if N = 2 and K = 2, then the possible dishes in lexicographic order are (1,1), (1,2), (2,1), (2,2). 
Given an integer L, determine the L^{th} possible dish in increasing order of quality.

------ 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.
Each test case description consists of a single line containing three integers N, K and L as described above.

------ Output Format ------ 

For each test case, print N space-separated integers in a single line describing the quantities of the ingredients for the Lth dish.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$L will not exceed the total number of possible dishes.$

------ subtasks ------ 

$For 20 points : N = 3, 2 ≤ K ≤ 102, 1 ≤ L ≤ 106$
$For 30 points : 1 ≤ N ≤ 102, 2 ≤ K ≤ 102, 1 ≤ L ≤ 104$
$For 50 points : 1 ≤ N ≤ 103, 2 ≤ K ≤ 103, 1 ≤ L ≤ 1018$

----- Sample Input 1 ------ 
4
3 3 1
3 3 2
3 3 3
3 3 4
----- Sample Output 1 ------ 
1 1 1
1 1 2
1 1 3
1 2 1
----- explanation 1 ------ 

First 4 dishes in order have ingredients (1,1,1), (1,1,2), (1,1,3), and (1,2,1).

----- Sample Input 2 ------ 
4
4 3 1
4 3 2
4 3 3
4 3 4
----- Sample Output 2 ------ 
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
----- explanation 2 ------ 

First 4 dishes in order have ingredients (1,1,1,1), (1,1,1,2), (1,1,1,3), and (1,1,2,1).

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(N, K, L) = list(map(int, input().split()))
	L -= 1
	digits = []
	while L:
		digits.append(int(L % K))
		L //= K
	digits = digits[::-1]
	digits = [1] * (N - len(digits)) + [1 + i for i in digits]
	print(*digits)


def get_arr(l, k):
	ans = []
	while l > 0:
		ans.append(l % k)
		l = l // k
	ans.reverse()
	return [i + 1 for i in ans]
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	if k == 1:
		print(1)
	else:
		ans = get_arr(l - 1, k)
		arr = [1] * (n - len(ans)) + ans
		print(*arr)


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	l -= 1
	f = [1 for i in range(n)]
	i = n - 1
	while l != 0:
		f[i] += l % k
		i -= 1
		l //= k
	for i in f:
		print(i, end=' ')
	print()


import sys
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	(n, k, l) = [int(x) for x in input().split()]
	l = l - 1
	ans = []
	while l:
		ans.append(l % k)
		l = l // k
	while len(ans) != n:
		ans.append(0)
	ans = ans[::-1]
	ans = [x + 1 for x in ans]
	print(*ans)


from math import log, ceil
t = int(input())
for _ in range(t):
	(n, k, l) = map(int, input().split())
	p = int(log(l, k)) + 1
	power = pow(k, p)
	ans = [1] * n
	x = n - p - 1
	while power != 0:
		ans[x] = ceil(l / power) if ceil(l / power) != 0 else k
		l = l - l // power * power
		power //= k
		x += 1
	print(*ans)


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())
for tastcas in range(int(input())):
	(n, k, l) = li()
	l -= 1
	ans = []
	while l != 0:
		ans.append((0, l % k))
		l //= k
	m = len(ans)
	while m != n:
		ans.append((0, 0))
		m += 1
	for i in range(n - 1, -1, -1):
		print(ans[i][1] + 1, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	l -= 1
	a = []
	while l != 0:
		a.insert(0, l % k)
		l //= k
	while len(a) != n:
		a.insert(0, 0)
	for j in a:
		print(j + 1, end=' ')
	print()


class Dish:

	def __init__(self, number_of_ingredients, maximum_quantity):
		self.n = number_of_ingredients
		self.k = maximum_quantity

	def cook_dish(self, l):
		outp = list()
		l -= 1
		while l > 0:
			next_digit = l % self.k
			l = (l - next_digit) // self.k
			outp.append(next_digit)
		outp.extend([0] * (self.n - len(outp)))
		return outp[::-1]

def solve(*args):
	(n, k, l) = args
	d = Dish(n, k)
	return d.cook_dish(l)

def do_codechef():
	for t in range(int(input())):
		(n, k, l) = map(int, input().split(' '))
		print(*[x + 1 for x in solve(n, k, l)])
do_codechef()
exit()


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	l = l - 1
	arr = []
	while l != 0:
		arr.insert(0, l % k)
		l = l // k
	while len(arr) != n:
		arr.insert(0, 0)
	for item in arr:
		print(item + 1, end=' ')
	print()


def getAnsw(l, k):
	answ = []
	while l > 0:
		answ.append(l % k)
		l = l // k
	answ.reverse()
	return [i + 1 for i in answ]
u = int(input())
for _ in range(u):
	(n, k, l) = map(int, input().split())
	if k == 1:
		print(1)
	else:
		answ = getAnsw(l - 1, k)
		arr = [1] * (n - len(answ)) + answ
		print(*arr)


t = int(input())
for i in range(t):
	nkl = input().split(' ')
	(n, k, l) = (int(nkl[0]), int(nkl[1]), int(nkl[2]))
	pows = []
	temp = k
	for j in range(n - 1):
		pows.append(temp)
		temp *= k
	pows.reverse()
	ans = []
	rank = 0
	for j in range(n - 1):
		for itr in range(1, k + 1):
			if l <= rank + pows[j]:
				ans.append(str(itr))
				break
			elif l > rank + pows[j]:
				rank += pows[j]
	for itr in range(1, k + 1):
		if l == rank + itr:
			ans.append(str(itr))
			break
	print(' '.join(ans))


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	ans = []
	l -= 1
	for i in range(n):
		v = pow(k, n - 1 - i)
		p = 0
		while v * (p + 1) <= l:
			p += 1
		l -= v * p
		ans.append(p + 1)
	print(*ans)


def str_base(number, base):
	(d, m) = divmod(number, base)
	if d > 0:
		return str_base(d, base) + [m]
	return [m]
for t in range(int(input())):
	(n, k, l) = map(int, input().split())
	cb = str_base(l - 1, k)
	ans = [1] * n
	for i in range(-1, -len(cb) - 1, -1):
		ans[i] += cb[i]
	print(' '.join(map(str, ans)))