Kuroni is the coordinator of the next Mathforces round written by the "Proof by AC" team. All the preparation has been done, and he is discussing with the team about the score distribution for the round.

The round consists of n problems, numbered from 1 to n. The problems are ordered in increasing order of difficulty, no two problems have the same difficulty. A score distribution for the round can be denoted by an array a_1, a_2, ..., a_n, where a_i is the score of i-th problem. 

Kuroni thinks that the score distribution should satisfy the following requirements:

  * The score of each problem should be a positive integer not exceeding 10^9. 
  * A harder problem should grant a strictly higher score than an easier problem. In other words, 1 ≤ a_1 < a_2 < ... < a_n ≤ 10^9. 
  * The balance of the score distribution, defined as the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ n and a_i + a_j = a_k, should be exactly m. 



Help the team find a score distribution that satisfies Kuroni's requirement. In case such a score distribution does not exist, output -1.

Input

The first and single line contains two integers n and m (1 ≤ n ≤ 5000, 0 ≤ m ≤ 10^9) — the number of problems and the required balance.

Output

If there is no solution, print a single integer -1.

Otherwise, print a line containing n integers a_1, a_2, ..., a_n, representing a score distribution that satisfies all the requirements. If there are multiple answers, print any of them.

Examples

Input


5 3


Output


4 5 9 13 18

Input


8 0


Output


10 11 12 13 14 15 16 17


Input


4 10


Output


-1

Note

In the first example, there are 3 triples (i, j, k) that contribute to the balance of the score distribution. 

  * (1, 2, 3) 
  * (1, 3, 4) 
  * (2, 4, 5)

Difficulty: HARD
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
(n, m) = map(int, input().split())

def limit(n):
	if n < 3:
		return 0
	if n ^ 1:
		return (n - 1) * (n - 1) >> 2
	else:
		return (n - 2) * n >> 2
if m > limit(n):
	print(-1)
	sys.exit()
elif not m:
	ans = [10 ** 8 + 1]
	while len(ans) < n:
		ans.append(ans[-1] + 10 ** 4)
	print(*ans)
	sys.exit()
L = 3
R = n + 1
while L + 1 < R:
	k = L + R >> 1
	if limit(k) > m:
		R = k
	else:
		L = k
k = L
ans = list(range(1, k + 1))
req = m - limit(k)
if req > 0:
	ans.append(ans[-1] + ans[-2 * req])
	k += 1
big_num = 10 ** 8 + 1
for i in range(k, n):
	ans.append(big_num)
	big_num += 10 ** 4
print(*ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
x = (n - 3) // 2
MAX = x * (x + 1)
if n % 2 == 1:
	MAX += (n - 1) // 2
else:
	MAX += (n - 1) // 2 * 2
if m > MAX:
	print(-1)
	sys.exit()
score = 0
x = 1
while score < m:
	x += 1
	score += (x - 1) // 2
LAST1 = x
x += (score - m) * 2
ANS = list(range(1, LAST1))
ANS.append(x)
for i in range(n - len(ANS)):
	ANS.append(10 ** 9 - i * 5001 - 1)
print(*sorted(ANS))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
ans = [1, 2]
tmp = 0
ind = 3
while tmp < M:
	t = (ind - 1) // 2
	if tmp + t <= M:
		ans.append(ind)
		tmp += t
		ind += 1
	else:
		delta = M - tmp
		ans.append(ind - 1 + (ind - 2 * delta))
		break
if M == 0:
	if N == 1:
		ans = [1]
if len(ans) > N:
	print(-1)
else:
	rem = []
	last = ans[-1]
	tmp = 10 ** 9
	for _ in range(N - len(ans)):
		rem.append(tmp)
		tmp -= last + 1
	ans = ans + rem[::-1]
	print(*ans)


def main():
	(n, m) = map(int, input().split())
	x = []
	i = 1
	while n > 0 and m >= len(x) // 2:
		m -= len(x) // 2
		n -= 1
		x.append(i)
		i += 1
	k = i - 1
	if m == 0 and n == 0:
		print(*x)
		return
	elif n == 0:
		print(-1)
		return
	else:
		x.append(2 * k - m * 2)
		n -= 1
	for i in range(n):
		x.append(20000 * (i + 1) + 1)
	print(*x)
main()


(n, m) = map(int, input().split())
mama_tabasza = 0
for i in range(n):
	mama_tabasza += i // 2
if m > mama_tabasza:
	print(-1)
else:
	odp = []
	i = 0
	dl_chuja = 0
	while dl_chuja + i // 2 <= m:
		odp.append(i + 1)
		dl_chuja += i // 2
		i += 1
	poz = m - dl_chuja
	if len(odp) > 0 and poz > 0:
		odp.append(2 * (odp[-1] - poz) + 1)
	dod = 10 ** 9
	k = len(odp)
	for j in range(n - k):
		odp.append(dod - 13337 * 13337 + 13337 * j)
	print(*odp[:n])


(n, m) = map(int, input().split(' '))
limit = 0
for i in range(3, n + 1):
	limit += (i - 1) // 2
if m > limit:
	print(-1)
else:
	a = [i for i in range(1, n + 1)]
	count = limit
	i = n
	while count > m:
		curr = (i - 1) // 2
		to_del = min(curr, count - m)
		if to_del == curr:
			a[i - 1] = 1000000000 - (n - i) * 10000
		else:
			a[i - 1] = a[i - 2] + a[i - 1 - 2 * (curr - to_del)]
		count -= to_del
		i -= 1
	print(' '.join(map(str, a)))


from sys import stdin
from bisect import bisect_left as bl
from bisect import bisect_right as br

def input():
	return stdin.readline()[:-1]

def intput():
	return int(input())

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

def intsput():
	return map(int, sinput())

class RangedList:

	def __init__(self, start, stop, val=0):
		self.shift = 0 - start
		self.start = start
		self.stop = stop
		self.list = [val] * (stop - start)

	def __setitem__(self, key, value):
		self.list[key + self.shift] = value

	def __getitem__(self, key):
		return self.list[key + self.shift]

	def __repr__(self):
		return str(self.list)

	def __iter__(self):
		return iter(self.list)

def dprint(*args, **kwargs):
	if debugging:
		print(*args, **kwargs)

def sigma(x):
	return x * (x + 1) // 2

def maxbalance(x):
	if x % 2 == 0:
		return sigma(x // 2 - 1) * 2
	else:
		x += 1
		return sigma(x // 2 - 1) * 2 - x // 2 + 1
debugging = 1
(n, balance) = intsput()
if maxbalance(n) < balance:
	print(-1)
	exit()
else:
	if n == 2:
		print('1 2')
		exit()
	elif n == 1:
		print('1')
		exit()
	largest = 2
	dist = [1, 2]
	k = 1
	while len(dist) < n:
		if balance:
			x = dist[-1] + 1
			can_create = (x - 1) // 2
			if can_create <= balance:
				dist.append(x)
				balance -= can_create
				largest = x
			else:
				dist.append(dist[-(balance * 2)] + dist[-1])
				balance = 0
		else:
			dist.append(10 ** 8 + 10 ** 4 * k + 1)
			k += 1
print(*dist)


def f(n):
	return (n - 1) ** 2 // 4
(N, M) = map(int, input().split())
if M > f(N):
	print(-1)
else:
	a = 1
	while f(a) < M:
		a += 1
	X = [i for i in range(1, a + 1)]
	X[-1] += (f(a) - M) * 2
	b = X[-1]
	l = N - len(X)
	X = X + [999999999 - i * (b + 1) for i in range(l)][::-1]
	print(*X)


def solve(n, m):
	if m > arr[n]:
		return (False, -1)
	ind = None
	for i in range(1, 5001):
		if arr[i] <= m and m <= arr[i + 1]:
			ind = i
			break
	ans = [i for i in range(1, ind + 1)]
	if m > arr[ind]:
		ans.append(ans[-(m - arr[ind]) * 2] + ans[-1])
	cur = 100000
	step = ans[-1] + 1
	while len(ans) < n:
		ans.append(cur)
		cur += step
	return (True, ans)
arr = [0]
for i in range(1, 5003):
	arr.append(arr[-1] + (i - 1) // 2)
(n, m) = map(int, input().split())
(flg, ans) = solve(n, m)
if flg == False:
	print(-1)
else:
	print(' '.join([str(x) for x in ans]))


(n, m) = map(int, input().split())
a = [0] * 5001
for i in range(1, 5001):
	a[i] = (i - 1) // 2
for i in range(1, 5001):
	a[i] = a[i] + a[i - 1]
ans = []
if m == 0:
	aa = 1
	for i in range(n):
		ans.append(aa)
		aa = aa + 4
	print(*ans)
elif m > a[n]:
	print(-1)
else:
	if m in a:
		ind = a.index(m)
		for i in range(1, ind + 1):
			ans.append(i)
	else:
		for i in range(1, 5000):
			if a[i] < m < a[i + 1]:
				for j in range(1, i + 1):
					ans.append(j)
				gap = m - a[i]
				ans.append(2 * i - 2 * gap + 1)
	l = len(ans)
	if l < n:
		aa = ans[l - 1]
		x = aa + 1
		for k in range(n - l):
			ans.append(aa + x)
			aa = aa + x
	print(*ans)


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
(n, m) = inm()
if n <= 2:
	if m > 0:
		print(-1)
	elif n == 1:
		print(1)
	else:
		print('1 2')
	exit()
for k in range(2502):
	p = k * (k - 1)
	if p >= m:
		od = False
		r = p - m
		break
	p = k * k
	if p >= m:
		od = True
		r = p - m
		break
if k > 2500 or 2 * k + (1 if od else 0) > n:
	print(-1)
	exit()
t = 2 * k + (1 if od else 0)
t = max(t, 1)
pad = ''
cnt = 0
for i in range(1, t):
	printn(pad + str(i))
	pad = ' '
	cnt += 1
printn(pad + str(t + 2 * r))
pad = ' '
cnt += 1
for i in range(cnt + 1, n + 1):
	printn(pad + str(10001 + 5001 * i))
print('')


from math import ceil, floor
(n, m) = map(int, input().split())
x = floor(m ** (1 / 2))
(k, d) = (0, 0)
if x * (x + 1) <= m:
	x += 1
if x * (x - 1) + x <= m:
	k = x * 2 + 1
	d = m - (x * (x - 1) + x)
else:
	k = x * 2
	d = m - x * (x - 1)
t = k // 2 - d
p = k + 1 + t * 2
y = n // 2
big = 10 ** 9 - (n - k - 1) * 5000
if y * (y - 1) + (n - 1) // 2 * (n % 2 == 1) < m:
	print(-1)
elif m == 0:
	for i in range(10 ** 9 - n, 10 ** 9):
		print(i, end=' ')
else:
	for i in range(1, k + 1):
		print(i, end=' ')
	if p <= k + k - 1:
		print(p, end=' ')
	else:
		k -= 1
	for i in range(n - k - 1):
		print(big, end=' ')
		big += 5000


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	(n, m) = map(int, input().split())
	if n < 3:
		if m == 0:
			print(*[1, 2][:n])
		else:
			print(-1)
		exit()
	ans = [1, 2]
	for i in range(3, n + 1):
		if i - 1 >> 1 >= m:
			ans.append(2 * i - 2 * m - 1)
			m = 0
			break
		ans.append(i)
		m -= i - 1 >> 1
	for i in range(n - len(ans)):
		ans.append(10 ** 8 + i * 10000)
	if m == 0:
		print(*ans)
	else:
		print(-1)
main()


import sys
import math
import itertools
(n, m) = map(int, input().split())
init = [1]
for i in range(1, n):
	if m == 0:
		break
	pairs = i // 2
	if m >= pairs:
		m -= pairs
		init.append(i + 1)
	else:
		init.append(i + 1 + 2 * (pairs - m))
		m = 0
if m != 0:
	print(-1)
	sys.exit()
nxt = 10000000 + 6000
while len(init) < n:
	init.append(nxt)
	nxt += 6000
for i in init:
	print(i, end=' ')


(n, m) = [int(x) for x in input().split()]
cur_add = 0
cur_bal = 0
cur_list = []
while len(cur_list) < n and cur_bal + cur_add <= m:
	cur_bal += cur_add
	cur_add += len(cur_list) % 2
	cur_list.append(len(cur_list) + 1)
if len(cur_list) == n and cur_bal < m:
	print(-1)
	import sys
	sys.exit()
if cur_bal != m:
	cur_list.append(cur_list[-1] + cur_list[-2 * (m - cur_bal)])
while len(cur_list) < n:
	cur_list.append(10 ** 8 + len(cur_list) * 10 ** 4)
print(*cur_list)


import sys
(n, m) = map(int, input().split())
nsum = 0
ans = []
for i in range(1, n + 1):
	if nsum + (i - 1) // 2 < m:
		ans.append(i)
		nsum += (i - 1) // 2
	else:
		ans.append(i - 1 + (i - (m - nsum) * 2))
		nsum = m
		break
maxi = ans[-1]
if nsum < m:
	print(-1)
	sys.exit()
cnt = 10 ** 9
while len(ans) < n:
	ans.append(cnt)
	cnt -= maxi + 1
ans.sort()
print(*ans)


(n, m) = map(int, input().split())
numList = [x + 1 for x in range(n)]
backdoor = []
count = sum([(i - 1) // 2 for i in range(1, n + 1)])
if count < m:
	exit(print(-1))
while count > m:
	lastpop = numList.pop()
	count -= (lastpop - 1) // 2
	if count >= m:
		if len(backdoor) == 0:
			backdoor.append(10 ** 9)
		else:
			backdoor.append(backdoor[-1] - 2 ** 16)
	else:
		gap = m - count
		backdoor.append(2 * (lastpop - gap) - 1)
		count += gap
while len(backdoor) > 0:
	numList.append(backdoor.pop())
print(' '.join([str(x) for x in numList]))


dic = {}
count = 0
for i in range(1, 5001):
	count += (i - 1) // 2
	dic[i] = count
(n, m) = map(int, input().split())
if m > dic[n]:
	print(-1)
elif m == 0:
	print(*[450000000 + i for i in range(n)])
else:
	ls = []
	flag = False
	for i in range(1, 5001):
		if dic[i] > m:
			flag = True
			break
		else:
			ls.append(i)
	if flag:
		m -= dic[i - 1]
	else:
		m -= dic[i]
	if m:
		ls.append(ls[-1] + ls[-2 * m])
	if len(ls) <= n:
		x = ls[-1] + ls[-2 * m]
		for i in range(n - len(ls)):
			ls.append(10 ** 7 + x * i)
		ls.sort()
		print(*ls)
	else:
		print(-1)


(N, K) = map(int, input().split())

def f(k):
	r = 0
	for i in range(1, k):
		r += i // 2
	return r
(mx, mn) = (N + 2, 0)
idx = N // 2
while mx - mn > 1:
	if f(idx) < K:
		(idx, mn) = ((idx + mx) // 2, idx)
		continue
	(idx, mx) = ((idx + mn) // 2, idx)
if idx + 1 > N:
	print(-1)
	import sys
	sys.exit()
rs = []
for i in range(idx):
	rs.append(i + 1)
rs.append(idx + 1 + 2 * (f(idx + 1) - K))
rs2 = []
for i in range(N - (idx + 1)):
	rs2.append(5000 + i)
rs = [10000 * x for x in rs]
print(*rs2 + rs)


def gen_sequence(size, balance):
	result = []
	for i in range(1, size + 1):
		triple_count = i - 1 >> 1
		if triple_count <= balance:
			result.append(i)
			balance -= triple_count
		else:
			break
	if len(result) == size and balance > 0:
		return [-1]
	if balance > 0:
		result.append(2 * (result[-1] - balance) + 1)
	delta = result[-1] + 1
	while len(result) < size:
		value = result[-1] + delta
		if value % 2 == 0:
			value += 1
		result.append(value)
	return result
(size, balance) = map(int, input().split())
for x in gen_sequence(size, balance):
	print(x, end=' ')
print()


(n, m) = map(int, input().split())
out = []
currCount = 0
currVal = 0
while currVal < n:
	nex = currVal // 2
	if nex + currCount <= m:
		currCount += nex
		currVal += 1
		out.append(currVal)
	else:
		break
need = m - currCount
if need > 0:
	nex = currVal // 2
	val = currVal + 1
	val += 2 * (nex - need)
	if nex > need:
		out.append(val)
		currCount += need
l = len(out)
if l > n or m != currCount:
	assert m > (n - 1) * (n - 1) // 4
	print(-1)
else:
	assert m <= (n - 1) * (n - 1) // 4
	lorg = max(out)
	diff = lorg + 1
	start = (lorg + diff) // diff
	start += 2
	start *= diff
	start += 1
	while l < n:
		l += 1
		out.append(start)
		start += diff
	assert len(out) == n
	for i in range(n - 1):
		assert out[i] < out[i + 1]
		assert 1 <= out[i]
		assert out[i + 1] <= 10 ** 9
	thing = set(out)
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if out[i] + out[j] in thing:
				count += 1
	assert count == m
	print(' '.join(map(str, out)))


import sys
(n, m) = map(int, input().split())
esum = 0
res = []
for i in range(1, n + 1):
	if esum + (i - 1) // 2 < m:
		res.append(i)
		esum += (i - 1) // 2
	else:
		res.append(i - 1 + (i - (m - esum) * 2))
		esum = m
		break
maxi = res[len(res) - 1]
if esum < m:
	print(-1)
	sys.exit()
count = 10 ** 9
while len(res) < n:
	res.append(count)
	count -= maxi + 1
res = sorted(res)
print(*res)


import math
import sys
(n, m) = [int(s) for s in input().split()]
ans = []
curr_balance = 0
for i in range(1, n + 1):
	new_balance = math.floor((i - 1) / 2)
	if curr_balance + new_balance > m:
		break
	curr_balance += new_balance
	ans.append(i)
if curr_balance < m:
	if len(ans) == n:
		print(-1)
		sys.exit()
	remaining_balance = m - curr_balance
	number_index = remaining_balance * 2 - 1
	if ans[-1 - number_index] + ans[-1] <= 1000000000:
		ans.append(ans[-1 - number_index] + ans[-1])
num_to_add = ans[-1] + 1
for i in range(len(ans) + 1, n + 1):
	if ans[-1] + num_to_add <= 1000000000:
		ans.append(ans[-1] + num_to_add)
	else:
		break
if len(ans) < n:
	print(-1)
	sys.exit()
for i in ans:
	print(i, ' ')


(n, m) = map(int, input().split())
ans = [i + 1 for i in range(n)]
max_cnt = 0
for i in range(n):
	max_cnt += i // 2
if max_cnt < m:
	print(-1)
	exit()
diff = 1
for i in range(n)[::-1]:
	cnt = i // 2
	if max_cnt - m == 0:
		continue
	if cnt <= max_cnt - m:
		ans[i] = 10 ** 9
		diff += 1
		max_cnt -= cnt
	else:
		cnt = max_cnt - m
		ans[i] = i + 1 + 2 * cnt
		max_cnt = m
for i in range(n):
	if ans[i] != 10 ** 9:
		ans[i] *= 5000
	else:
		ans[i] = ans[i - 1] + 1
print(*ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

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

def mdata():
	return list(map(int, data().split()))

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

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = int(1000000000.0) + 7
INF = 10 ** 8
(n, m) = mdata()
if n == 1 and m == 0:
	out(1)
	exit()
l = []
k = math.floor(((1 + 4 * m) ** 0.5 - 1) / 2)
if k > n:
	out(-1)
	exit()
l = list(range(1, 2 * k + 3))
m -= k * (k + 1)
while m:
	l.append(l[-1] + l[max(0, l[-1] - 2 * m)])
	m -= min(m, l[-1] // 2)
if len(l) > n:
	out(-1)
	exit()
i = 0
t = l[-1]
while len(l) < n:
	l.append(INF + i * (t + 1))
	i += 1
outl(l)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List
(N, M) = map(int, input().split())
A = [x + 1 for x in range(N)]
B = []
count = sum([(i - 1) // 2 for i in range(1, N + 1)])
if count < M:
	print(-1)
	exit(0)
while count > M:
	lastpop = A.pop()
	count -= (lastpop - 1) // 2
	if count >= M:
		if len(B) == 0:
			B.append(10 ** 9)
		else:
			B.append(B[-1] - 2 ** 16)
	else:
		gap = M - count
		B.append(2 * (lastpop - gap) - 1)
		count += gap
A += B[::-1]
print(' '.join(map(str, A)))