You are given positive integers N and K. 

You have to construct an array A of length N such that :
1 ≤ A_{i} ≤ 10^{18}
\sum_{i=1}^{N} \sum_{j=i}^{N} F(i,j) = K, where F(i,j) denotes the [gcd] of all elements of the subarray A[i, j].

If multiple such arrays exist, print any.  
Report -1 if no such array exists.  

Note that A[l, r] denotes the subarray [A_{l} ,A_{l+1}, \ldots, A_{r-1}, A_{r}].

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of single line of input.
- The only line of each test case contains two space-separated integers N and K — the number of elements and required sum.

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

For each test case, output on a new line N space-separated integers, denoting array A.  
Report -1 if no such array exists.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$1 ≤ K ≤ 10^{18}$
- The sum of $N$ over all test cases won't exceed $1000$.

----- Sample Input 1 ------ 
3
1 5
2 4
3 1

----- Sample Output 1 ------ 
5
1 2
-1

----- explanation 1 ------ 
Test case $1$: The only possible array of size $1$ such that the sum of gcd of all subarrays is $5$ is $A = [5]$.

Test case $2$: Consider an array of size $2$ as $A = [1, 2]$. The subarrays of the array are:
- $[1]$: The gcd of this subarray is $1$.
- $[1, 2]$: The gcd of this subarray is $gcd(1, 2) = 1$.
- $[2]$: The gcd of this subarray is $2$.

The sum of gcd of all subarrays is $1+1+2= 4$.

Test case $3$: It can be proven that there exists no subarray of size $3$ such that the sum of gcd of all subarrays of the array is $1$.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	d = n * (n + 1) / 2
	if k < d:
		print(-1)
		continue
	ans = int(k - d + 1)
	print(ans, end=' ')
	for i in range(n - 1):
		print(1, end=' ')
	print('')


for _ in range(int(input())):
	(nog, kou) = map(int, input().split())
	vok = nog * (nog + 1) // 2 - 1
	if kou < nog * (nog - 1):
		print(-1)
	else:
		for m in range(nog - 1):
			print('1 ', end='')
		print(kou - vok)


for qwertyuio in range(int(input())):
	(x, y) = map(int, input().split())
	g = x * (x + 1) // 2
	if y < g:
		print(-1, '\n')
	else:
		for n in range(x - 1):
			print('1', end=' ')
		print(y - g + 1)


n_cases = int(input())
for _ in range(n_cases):
	(n, k) = [int(x) for x in input().split()]
	min_gcd_sum = n * (n + 1) // 2
	if k < min_gcd_sum:
		print('-1')
	else:
		x = k - min_gcd_sum + 1
		arr = [1] * (n - 1)
		arr.append(x)
		print(' '.join((str(x) for x in arr)))


test_cases = int(input())
for i in range(test_cases):
	(n, k) = map(int, input().split())
	m = n * (n + 1) // 2
	if n == 1:
		print(k)
	elif k < pow(2, n) - 1:
		print(-1)
	else:
		print('1 ' * (n - 1), end='')
		print(k - m + 1)


def sol(n, k):
	if k < n * (n + 1) // 2:
		return -1
	a = [k - n * (n + 1) // 2 + 1]
	b = [1 for _ in range(n - 1)]
	return ' '.join([str(x) for x in a + b])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(sol(n, k))


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	x = n * (n + 1) // 2
	list1 = []
	for i in range(n):
		list1.append(1)
	if k < x:
		print('-1')
	elif k == x:
		print(list1)
	else:
		if n == 1:
			list1[0] = k
		else:
			d = k - x + 1
			list1[-1] = d
		print(*list1)


T = int(input())
for j in range(0, T):
	temp = input().split()
	N = int(temp[0])
	K = int(temp[1])
	if N * (N + 1) // 2 > K:
		print(-1)
	else:
		answer = [1] * (N - 1)
		answer.append(K - N * (N + 1) // 2 + 1)
		print(*answer)


t = int(input())
while t > 0:
	inp = [int(i) for i in input().split(' ')]
	n = inp[0]
	k = inp[1]
	min_possible = n * (n + 1) / 2
	diff = k - min_possible
	if k < min_possible:
		print(-1)
	else:
		for i in range(n):
			if i == 0 and i == n - 1:
				print(int(diff + 1))
			elif i == 0:
				print(int(diff + 1), end=' ')
			elif i == n - 1:
				print(int(1))
			else:
				print(int(1), end=' ')
	t -= 1


T = int(input())
while T > 0:
	(n, k) = map(int, input().split())
	s = n * (n + 1) // 2
	if k < s:
		print(-1)
	else:
		for i in range(n - 1):
			print(1, end=' ')
		print(k - s + 1)
	T -= 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = n * (n + 1) // 2
	if k < s:
		print(-1)
	else:
		for i in range(n - 1):
			print(1, end=' ')
		print(k - s + 1)


def main():
	for __ in range(int(input())):
		(n, k) = map(int, input().split())
		min_total = n * (n + 1) // 2
		if k < min_total:
			print(-1)
		else:
			ans = []
			for __ in range(n - 1):
				ans.append(1)
			ans.append(k - min_total + 1)
			for i in ans:
				print(i, end=' ')
			print('\n')
main()


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = a[1]
	n = a[0]
	s = n * (n + 1) // 2
	if k < s:
		print(-1)
	else:
		for j in range(n - 1):
			print(1, end=' ')
		print(k - s + 1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = n * (n + 1) // 2
	if k < s:
		print(-1)
	else:
		print('1 ' * (n - 1) + f'{k - s + 1}')


for i in range(int(input())):
	l = list(map(int, input().split()))
	s = l[0] * (l[0] + 1)
	s = s // 2
	if l[1] < s:
		print('-1')
	else:
		a = l[1] - s + 1
		print('1 ' * (l[0] - 1) + str(a))


aux = [0] * 101
aux[0] = 0
for i in range(1, 101):
	aux[i] = int(i * (i + 1) / 2)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k < aux[n]:
		print('-1')
	else:
		for i in range(1, n):
			print('1', end=' ')
		print(int(k - aux[n] + 1))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = n * (n + 1)
	s = s // 2
	if k < s:
		print('-1')
	else:
		l = k - s + 1
		print('1 ' * (n - 1) + str(l))


t = int(input())
for r in range(t):
	(n, k) = map(int, input().split())
	a = n * (n + 1) // 2
	if a > k:
		print(-1)
	else:
		print(str(k - a + 1) + ' 1' * (n - 1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = n * (n + 1) // 2
	if a > k:
		print(-1)
	else:
		print('1 ' * (n - 1) + str(k - a + 1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = n * (n + 1) // 2
	if a > k:
		print(-1)
	else:
		for i in range(n - 1):
			print(1, end=' ')
		print(k - a + 1)


for _ in range(int(input())):
	K = list(map(int, input().split()))
	N = K[0]
	g = K[1]
	gcd = N * (N + 1) // 2
	if g < gcd:
		print(-1)
	else:
		for i in range(N - 1):
			print(1, end=' ')
		print(g - gcd + 1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	g = a * (a + 1) // 2
	if b < g:
		print(-1)
	else:
		for i in range(a - 1):
			print('1', end=' ')
		print(b - g + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	n1 = n * (n + 1) / 2
	if k < n1:
		print(-1)
	else:
		p = int(k - n1 + 1)
		ans = []
		ans.append(p)
		for i in range(n - 1):
			ans.append(1)
		print(*ans, sep=' ')


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	atleast = n * (n + 1) // 2
	if atleast > k:
		print(-1)
	else:
		arr = [1 for i in range(n - 1)]
		arr.append(k - atleast + 1)
		print(*arr)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	temp = N * (N + 1) // 2
	if K < N * (N + 1) // 2:
		print('-1')
	else:
		for i in range(N - 1):
			print('1', end=' ')
		print(1 - temp + K)


test = int(input())
for t in range(test):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	min_gcd = n * (n + 1) // 2
	if k < min_gcd:
		print(-1)
	else:
		for i in range(n - 1):
			print(1, end=' ')
		print(k - min_gcd + 1)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	l = []
	s = n * (n + 1) // 2
	if s > m:
		print(-1)
	else:
		for i in range(n - 1):
			print(1, end=' ')
		print(m - s + 1)


def gcdSubarray(n, k):
	if k < n * (n + 1) // 2:
		print(-1)
		return
	arr = [1] * (n - 1)
	x = k - (n * (n + 1) // 2 - 1)
	arr.append(x)
	print(*arr)
	return
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	gcdSubarray(n, k)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = n * (n + 1) // 2
	if k < a:
		print('-1')
	elif k == a:
		print(c)
	else:
		d = k - a + 1
		print('1 ' * (n - 1), end='')
		print(d)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	if n == 1:
		print(k)
	else:
		i = 1
		res = 1
		if k < n * (n + 1) // 2 + 1:
			print(-1)
		else:
			res_arr = [1] * (n - 1) + [k - n * (n + 1) // 2 + 1]
			print(*res_arr)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	if k < n * (n + 1) // 2 + 1:
		print(-1)
	else:
		result_arr = [1] * (n - 1) + [k - (n + 1) * n // 2 + 1]
		print(*result_arr)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k < n * (n - 1) // 2 + n:
		print(-1)
	else:
		ans = [1] * (n - 1) + [k - (n * (n - 1) // 2 + n) + 1]
		print(*ans)


def solve(n, k):
	if k < n * (n + 1) // 2:
		return [-1]
	else:
		if n == 1:
			return [k]
		t = k - n * (n + 1) // 2
		res = [1] * (n - 1)
		res.append(t + 1)
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(*solve(n, k))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = n * (n + 1) // 2
	if k < l:
		print('-1')
	else:
		for i in range(1, n):
			print('1', end=' ')
		k = k - (l - 1)
		print(k)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	sn = N * (N + 1) // 2
	ans.append([-1] if sn > K else [1] * (N - 1) + [K - sn + 1])
outpltlt(ans)


def solution():
	(n, k) = map(int, input().split())
	if k < n * (n + 1) // 2:
		print(-1)
	else:
		print(*[1] * (n - 1) + [k - n * (n - 1) // 2 - (n - 1)])
t = int(input())
while t > 0:
	t = t - 1
	solution()


for i in range(int(input())):
	(N, K) = map(int, input().split(' '))
	total = N * (N + 1) // 2
	ans = []
	if K < total:
		print(-1)
	else:
		rem = K - total + 1
		for j in range(N - 1):
			ans.append(1)
		ans.append(rem)
		print(*ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	n = a * (a + 1) // 2
	if b < n:
		print('-1')
	else:
		for i in range(a - 1):
			print('1', end=' ')
		print(b - n + 1)


import sys
next((f := sys.stdin))
for s in f:
	(n, k) = map(int, s.split())
	m = k - n * (n + 1) // 2 + 1
	print(*([m] + [1] * (n - 1) if m > 0 else [-1]))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = n * (n + 1) // 2
	if k == 1 and n > 1:
		print(-1)
	elif x > k:
		print(-1)
	elif n == 1:
		print(k)
	else:
		a = k - x + 1
		arr = [1] * (n - 1)
		arr.append(a)
		print(*arr)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	x = int(n * (n + 1) / 2)
	if x > k:
		print('-1')
	else:
		print('1 ' * (n - 1) + str(k - x + 1))


T = int(input())
while T:
	(A, K) = list(map(int, input().split()))
	n = int(A * (A + 1) / 2)
	if K < n:
		print(-1)
	else:
		arr = [1] * A
		arr[-1] = K - n + 1
		print(*arr)
	T = T - 1


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mu = n * (n + 1) // 2 - 1
	if k - mu > 0:
		for i in range(n - 1):
			print('1', end=' ')
		print(k - mu)
	else:
		print('-1')


import math
a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	if c < b * (b + 1) // 2:
		print('-1')
	else:
		s = 0
		d = []
		for j in range(b - 1):
			print('1', end=' ')
		print(c - b * (b + 1) // 2 + 1)