You are given three integers $n$, $l$, and $r$. You need to construct an array $a_1,a_2,\dots,a_n$ ($l\le a_i\le r$) such that $\gcd(i,a_i)$ are all distinct or report there's no solution.

Here $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $n$, $l$, $r$ ($1 \le n \le 10^5$, $1\le l\le r\le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, if there is no solution, print "NO" (without quotes). You can print letters in any case (upper or lower).

Otherwise, print "YES" (without quotes). In the next line, print $n$ integers $a_1,a_2,\ldots,a_n$ — the array you construct.

If there are multiple solutions, you may output any.


-----Examples-----

Input
4
5 1 5
9 1000 2000
10 30 35
1 1000000000 1000000000
Output
YES
1 2 3 4 5
YES
1145 1926 1440 1220 1230 1350 1001 1000 1233
NO
YES
1000000000


-----Note-----

In the first test case, $\gcd(1,a_1),\gcd(2,a_2),\ldots,\gcd(5,a_5)$ are equal to $1$, $2$, $3$, $4$, $5$, respectively.

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
from sys import stdin
rd = stdin.readline
for _ in range(int(rd())):
	(n, l, r) = map(int, rd().split())
	lis = []
	for i in range(1, n + 1):
		temp = ((l - 1) // i + 1) * i
		if temp > r:
			print('NO')
			break
		lis.append(str(temp))
	else:
		print('YES')
		print(' '.join(lis))


import sys
import math
T = int(sys.stdin.readline())

def solve(N, L, R):
	Ans = []
	for i in range(1, N + 1):
		first_mul_above_L = math.ceil(L / i) * i
		if first_mul_above_L <= R:
			Ans.append(first_mul_above_L)
		else:
			return None
	return Ans
for _ in range(T):
	(N, L, R) = list(map(int, sys.stdin.readline().split()))
	Seq = solve(N, L, R)
	if Seq is None:
		print('NO')
	else:
		print('YES')
		print(' '.join([str(x) for x in Seq]))


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
from math import gcd
t = num_inp()
for _ in range(t):
	(n, l, r) = sp_inp()
	arr = []
	for i in range(1, n + 1):
		val = ((l - 1) // i + 1) * i
		if val >= l and val <= r:
			arr.append(val)
		else:
			print('NO')
			break
	else:
		print('YES')
		print(' '.join(map(str, arr)))


m = int(input())

def func(t, l, r):
	res = []
	for i in range(1, t + 1):
		if l % i == 0:
			n = l
		else:
			n = (l // i + 1) * i
		if n > r:
			print('NO')
			return
		res.append(n)
	print('YES')
	print(' '.join([str(i) for i in res]))
for _ in range(m):
	(n, l, r) = [int(i) for i in input().split()]
	func(n, l, r)


for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	t = l
	l1 = []
	for j in range(1, n + 1):
		k = l % j
		if k == 0:
			l1.append(l)
		elif l + (j - k) <= r:
			l1.append(l + (j - k))
		else:
			break
	if len(l1) < n:
		print('NO')
	else:
		print('YES')
		k = ' '.join((str(x) for x in l1))
		print(k)


for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	c = 1
	g = []
	for i in range(1, n + 1):
		if l % i == 0:
			g.append(str(l))
		else:
			x = l // i + 1
			x = x * i
			if x <= r:
				g.append(str(x))
	if len(g) == n:
		print('YES')
		print(' '.join(g))
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(n, l, r) = [int(c) for c in input().split(' ')]
	sol = []
	flag = True
	for i in range(n, 0, -1):
		cand = l + (i - l % i) % i
		assert not cand % i
		if cand > r:
			print('NO')
			flag = False
			break
		else:
			sol.append(str(cand))
	if flag:
		sol.reverse()
		print('YES')
		print(' '.join(sol))


t = int(input())
res = []
for _ in range(t):
	(n, l, r) = list(map(int, input().split()))
	a = []
	s = set()
	for i in range(1, n + 1):
		x = -(l // -i) * i
		if x <= r:
			a.append(x)
	if len(a) == n:
		res.append('YES')
		res.append(a)
	else:
		res.append('NO')
for i in res:
	if isinstance(i, list):
		print(*i)
	else:
		print(i)


import math
t = int(input())
for jj in range(t):
	(n, l, r) = [int(i) for i in input().split(' ')]
	p = []
	for i in range(1, n + 1):
		item = l % i
		if item == 0:
			p.append(l)
		elif l + (i - item) <= r:
			p.append(l + i - item)
		else:
			break
	if len(p) < n:
		print('NO')
	else:
		print('YES')
		a = [str(i) for i in p]
		print(' '.join(a))


import sys

def input():
	return sys.stdin.readline()[:-1]
t = int(input())
for _ in range(t):
	(n, l, r) = map(int, input().split())
	ans = []
	flg = 'YES'
	for i in range(n):
		m = (l - 1) // (i + 1) + 1
		if m * (i + 1) <= r:
			ans.append(m * (i + 1))
		else:
			flg = 'NO'
	print(flg)
	if flg == 'YES':
		print(*ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	(n, l, r) = map(int, input().split())
	flag = True
	ans = []
	for j in range(1, n + 1):
		y = (l + j - 1) // j
		x = y * j
		if x > r:
			flag = False
			break
		ans.append(x)
	if flag:
		print('YES')
		print(' '.join(map(str, ans)))
	else:
		print('NO')


for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	fl = True
	a = [0] * n
	for i in range(n):
		bot = (l + i) // (i + 1) * (i + 1)
		if bot > r:
			fl = False
			break
		a[i] = bot
	if fl:
		print('YES')
		print(' '.join((str(i) for i in a)))
	else:
		print('NO')


t = int(input())
for tt in range(t):
	(n, l, r) = map(int, input().split())
	arr = [0] * n
	for s in range(1, n + 1):
		k = l - l % s
		if l % s != 0:
			k += s
		if k > r:
			print('NO')
			break
		arr[s - 1] = k
	else:
		print('YES')
		print(' '.join(map(str, arr)))


n_tests = int(input().strip())
for _ in range(n_tests):
	nums = [int(x) for x in input().strip().split(' ')]
	n = nums[0]
	l = nums[1]
	r = nums[2]
	feasible = True
	res = [0] * n
	for i in reversed(range(1, n + 1)):
		if l % i == 0:
			res[i - 1] = str(l)
		elif r % i == 0:
			res[i - 1] = str(r)
		elif r // i > l // i:
			res[i - 1] = str((l // i + 1) * i)
		else:
			feasible = False
			break
	if feasible:
		print('YES')
		print(' '.join(res))
	else:
		print('NO')


t = int(input())
while t:
	s = input().split()
	(n, l, r) = map(int, s)
	arr = []
	ans = 'YES'
	for i in range(1, n + 1):
		if l % i == 0:
			num = l
		else:
			num = i - l % i + l
		if num > r:
			ans = 'NO'
			break
		arr.append(num)
	if ans == 'YES':
		print(ans)
		print(' '.join(list(map(str, arr))))
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	(n, l, r) = map(int, input().split())
	ans = [l]
	ji = []
	for i in range(1, n):
		a = l % (i + 1)
		if a == 0:
			ans.append(l)
		else:
			ans.append(l + i + 1 - l % (i + 1))
	if max(ans) > r:
		print('NO')
	else:
		print('YES')
		print(' '.join(map(str, ans)))


for i in range(int(input())):
	(n, l, r) = map(int, input().split())
	a = []
	for i in range(n):
		i1 = i + 1
		if l % i1 == 0:
			a.append(l)
		else:
			k = l + i1 - l % i1
			if k > r:
				print('NO')
				break
			else:
				a.append(k)
	else:
		print('YES')
		print(' '.join([str(i) for i in a]))


for i in range(int(input())):
	(n, l, r) = map(int, input().split())
	li = str(l)
	x = l
	ans = 'YES'
	if n == 1:
		print('YES')
		print(l)
		continue
	for i in range(2, n + 1):
		if l % i == 0:
			li += ' ' + str(l)
		else:
			y = l // i
			x = int((y + 1) * i)
			li += ' ' + str(x)
		if x > r:
			ans = 'NO'
			break
	print(ans)
	if ans == 'YES':
		print(li)


j = 0
t = int(input())
while j < t:
	(n, l, r) = map(int, input().split())
	b = True
	L = []
	for i in range(n, 0, -1):
		a = l // i
		if a * i < l:
			if l <= (a + 1) * i <= r:
				L.append((a + 1) * i)
			else:
				b = False
				break
		elif l <= a * i <= r:
			L.append(a * i)
		else:
			b = False
			break
	if not b:
		print('NO')
	else:
		L.reverse()
		print('YES')
		print(' '.join(map(str, L)))
	j += 1


import math
t = int(input())

def solve():
	(n, l, r) = map(int, input().split())
	lst = []
	for i in range(1, n + 1):
		k = math.ceil(l / i) * i
		if k >= l and k <= r:
			lst.append(k)
		else:
			print('NO')
			return
	print('YES')
	print(' '.join((str(ele) for ele in lst)))
while t:
	solve()
	t -= 1


def sol(n, l, r):
	arr = []
	for i in range(1, n + 1):
		num = i * (l // i + 1 if l % i != 0 else l // i)
		if num > r:
			return (0, [])
		arr.append(num)
	return (1, arr)
x = int(input())
for _ in range(x):
	(n, l, r) = list(map(int, input().split()))
	(found, arr) = sol(n, l, r)
	if found:
		print('YES')
		print(' '.join(map(str, arr)))
	else:
		print('NO')


import sys
import math
t = int(sys.stdin.readline())
for i in range(t):
	(n, l, r) = map(int, sys.stdin.readline().split())
	se = set()
	ans = []
	dic = {}
	for j in range(2, n + 1):
		dic[j] = []
	for j in range(1, n + 1):
		rem = l % j
		if rem > 0:
			ele = l + j - rem
		else:
			ele = l
		if ele <= r:
			ans.append(ele)
	if len(ans) == n:
		print('YES')
		print(*ans)
	else:
		print('NO')


for _ in range(int(input())):
	(n, l, r) = list(map(int, input().split()))
	g = ''
	z = ''
	for i in range(1, n + 1):
		if l % i == 0:
			z += str(l)
			z += ' '
		else:
			w = l % i
			w = i - w
			if l + w > r:
				g = 'break'
				break
			else:
				z += str(l + w)
				z += ' '
	if g == 'break':
		print('NO')
	else:
		print('YES')
		print(z)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	(n, l, r) = map(int, input().split())
	f = 1
	arr = []
	for i in range(1, n + 1):
		if l <= ((l - 1) // i + 1) * i <= r:
			arr.append(((l - 1) // i + 1) * i)
		else:
			f = 0
	if f == 0:
		print('NO')
	else:
		print('YES')
		print(*arr)


t = int(input())
for _ in range(t):
	(n, l, r) = list(map(int, input().split(' ')))
	a = []
	if r < n:
		print('NO')
		continue
	for i in range(1, n + 1):
		if l % i == 0:
			a.append(str(l))
		else:
			b = (l // i + 1) * i
			if b > r:
				print('NO')
				break
			else:
				a.append(str(b))
	else:
		print('YES')
		print(' '.join(a))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for _ in range(t):
	(n, l, r) = mp()
	f = 0
	k = []
	for i in range(1, n + 1):
		if l % i == 0:
			k.append(l)
		else:
			s = l // i
			if (s + 1) * i <= r:
				k.append((s + 1) * i)
			else:
				f = 1
				break
	if f == 1:
		pr('NO')
	else:
		pr('YES')
		print(*k)


import sys
input = sys.stdin.readline

def helper(n, x):
	if x > n:
		return x
	z = x // 2
	n = n + z
	n = n - n % x
	return n
for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	a = [0] * (n + 1)
	ok = True
	for i in range(1, n + 1):
		a[i] = helper(l, i)
		if a[i] < l:
			a[i] += i
		if a[i] > r:
			ok = False
			break
	if ok == False:
		print('NO')
	else:
		print('YES')
		print(*a[1:])


for t in range(int(input())):
	(n, l, r) = map(int, input().split())
	if n == 1:
		print('YES')
		print(l)
	else:
		ans = [l] * n
		f = True
		for i in range(1, n + 1):
			if ans[i - 1] % i == 0:
				pass
			elif ans[i - 1] + (i - ans[i - 1] % i) <= r:
				ans[i - 1] += i - ans[i - 1] % i
			else:
				f = False
				break
		if f:
			print('YES')
			print(' '.join(map(str, ans)))
		else:
			print('NO')


def divisible(n, r):
	if n % r == 0:
		return n // r
	else:
		return n // r + 1
t = int(input())
while t > 0:
	(n, l, r) = list(map(int, input().split(' ')))
	ans = ''
	temp1 = 0
	for i in range(1, n + 1):
		temp = divisible(l, i)
		temp = temp * i
		if temp > r:
			print('NO')
			temp1 = 1
			break
		ans += str(temp) + ' '
	if temp1 == 0:
		print('YES')
		print(ans)
	t -= 1


def solve():
	ans = []
	for i in range(1, n + 1):
		temp = l % i
		x = l
		if temp:
			x += i - temp
		if x > r:
			print('NO')
			return
		ans.append(x)
	print('YES')
	print(*ans)
for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	solve()


import math
import collections
import itertools
import functools

def fun(t):
	(n, l, r) = map(int, input().split(' '))
	arr = []
	for i in range(1, n + 1):
		if l % i == 0:
			arr.append(l)
		else:
			k = l + i - l % i
			if k > r:
				print('NO')
				return
			else:
				arr.append(k)
	print('YES')
	print(*arr)
for tc in range(int(input())):
	fun(tc)


def ro(l, i):
	if not i:
		return l
	rem = l % i
	if not rem:
		return l
	return l + i - rem

def solve():
	(n, l, r) = map(int, input().split())
	res = []
	d = r - l
	can = True
	for i in range(1, n + 1):
		rem = ro(l, i)
		if rem > r:
			can = False
			break
		res.append(rem)
	if not can:
		print('NO')
	else:
		print('YES')
		print(*res)
	return

def main():
	for _ in range(int(input())):
		solve()
	return
main()


for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	f = []
	flag = True
	for i in range(1, n + 1):
		if l % i == 0:
			f.append(l)
		else:
			ans = (l // i + 1) * i
			if ans > r:
				flag = False
			else:
				f.append(ans)
	if flag:
		print('YES')
		print(*f)
	else:
		print('NO')


for i in range(int(input())):
	(n, l, r) = map(int, input().split())
	f = []
	k = 1
	for j in range(1, n + 1):
		f += [(l - 1) // j * j + j]
		if f[-1] > r:
			k = 0
	if k:
		print('YES')
		print(*f)
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, l, r) = map(int, input().split())
	res = []
	flag = 0
	for j in range(1, n + 1):
		val = l + (j - l % j) if l % j != 0 else l
		if val <= r:
			res.append(val)
		else:
			flag = 1
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')
		print(*res)


import sys
import math

def diff_gcds(n, l, r):
	result = []
	for k in range(1, n + 1):
		lower = math.ceil(l / k)
		upper = math.floor(r / k)
		if lower > upper:
			return 'NO'
		else:
			result.append(lower * k)
	return result
input = list(map(int, sys.stdin.read().split()))
n = input[0]
data = input[1:]
cases = list(zip(data[0:3 * n:3], data[1:3 * n:3], data[2:3 * n:3]))
for i in cases:
	(n, l, r) = i
	output = diff_gcds(n, l, r)
	if output == 'NO':
		print(output)
	else:
		print('YES')
		for j in output:
			print(j, end=' ')
		print('')


t = int(input())
for i in range(t):
	(n, l, r) = map(int, input().split())
	m = []
	for i in range(1, n + 1):
		if l % i == 0:
			m.append(l)
		else:
			a = l // i
			b = i * (a + 1)
			if b <= r:
				m.append(b)
			else:
				print('NO')
				break
	else:
		print('YES')
		print(*m)


t = int(input())
for i in range(t):
	(n, l, r) = map(int, input().split())
	ans = []
	for i in range(1, n + 1):
		if l % i == 0:
			ans.append(l)
		else:
			ans.append(l + (i - l % i))
	if max(ans) <= r and min(ans) >= l:
		print('YES')
		print(*ans)
	else:
		print('NO')


for t in range(int(input())):
	(n, l, r) = map(int, input().split())
	k = []
	cnt = 0
	for i in range(1, n + 1):
		if l % i == 0:
			k.append(l)
		else:
			x = (l // i + 1) * i
			if x >= l and x <= r:
				k.append(x)
			else:
				cnt = 1
	if cnt:
		print('NO')
	else:
		print('YES')
		print(*k)


for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	arr = []
	for i in range(1, a + 1):
		arr.append(b + i - (b - 1) % i - 1)
	if max(arr) <= c:
		print('YES')
		print(*arr)
	else:
		print('NO')


def test():
	(n, l, r) = [int(i) for i in input().split()]
	li = [0]
	for i in range(1, n + 1):
		li.append(((l - 1) // i + 1) * i)
		if li[i] > r:
			print('NO')
			return
	print('YES')
	for i in range(1, n + 1):
		print(li[i], end=' ')
	print('')
	return
t = int(input())
for i in range(t):
	test()


tt = int(input())
for _ in range(tt):
	(n, l, r) = map(int, input().split())
	arr = [0] * n
	flag = False
	for i in range(n):
		arr[i] = ((l - 1) // (i + 1) + 1) * (i + 1)
		if not l <= arr[i] <= r:
			print('NO')
			flag = True
			break
	if not flag:
		print('YES')
		print(*arr)


def calc(n, l, r):
	b = []
	for i in range(1, n + 1):
		x = ((l - 1) // i + 1) * i
		if x <= r:
			b.append(x)
	if len(b) < n:
		print('NO')
	else:
		print('YES')
		print(*b)
c = int(input())
for i in range(0, c):
	a = list(map(int, str(input()).split(' ')))
	calc(a[0], a[1], a[2])


tt = 1
tt = int(input())
for _ in range(tt):
	(n, l, r) = map(int, input().split())
	ch = 1
	ans = [0] * n
	for i in range(n):
		j = i + 1
		num = ((l - 1) // j + 1) * j
		if l <= num <= r:
			ans[i] = num
		else:
			ch = 0
	if ch:
		print('YES')
		print(*ans)
	else:
		print('NO')