For a permutation P[1... N] of integers from 1 to N, function f is defined as follows:

 $f(i, j) = \left\{\begin{array}{ll}{P [ i ]} & {\text{if} j = 1} \\{f(P [ i ], j - 1)} & {\text{otherwise}} \end{array} \right.$ 

Let g(i) be the minimum positive integer j such that f(i, j) = i. We can show such j always exists.

For given N, A, B, find a permutation P of integers from 1 to N such that for 1 ≤ i ≤ N, g(i) equals either A or B.


-----Input-----

The only line contains three integers N, A, B (1 ≤ N ≤ 10^6, 1 ≤ A, B ≤ N).


-----Output-----

If no such permutation exists, output -1. Otherwise, output a permutation of integers from 1 to N.


-----Examples-----
Input
9 2 5

Output
6 5 8 3 4 1 9 2 7
Input
3 2 1

Output
1 2 3 


-----Note-----

In the first example, g(1) = g(6) = g(7) = g(9) = 2 and g(2) = g(3) = g(4) = g(5) = g(8) = 5 

In the second example, g(1) = g(2) = g(3) = 1

Difficulty: MEDIUM_HARD
Tags: Complete search

Constructive algorithms
Skill types: Complete search

Starter code:

Solutions:
from sys import stdin, stdout
(n, a, b) = map(int, input().split())
found = False
for x in range(n + 1):
	if (n - a * x) % b == 0:
		y = (n - a * x) // b
		if y >= 0:
			found = True
			break
if not found:
	print(-1)
	exit()
ans = []
(l, r) = (0, 1)
for _ in range(x):
	l = r
	r = l + a
	for i in range(l, r):
		if i + 1 == r:
			ans.append(l)
		else:
			ans.append(i + 1)
for _ in range(y):
	l = r
	r = l + b
	for i in range(l, r):
		if i + 1 == r:
			ans.append(l)
		else:
			ans.append(i + 1)
print(*ans)


from math import gcd as gcd
(n, a, b) = map(int, input().split())
ma = max(a, b)
mi = min(a, b)
t = 1
if n % gcd(a, b) != 0:
	print(-1)
else:
	ab = [0] * (n + 1)
	for i in range(0, 10 ** 6 + 1):
		if (n - ma * i) % mi == 0 and (n - ma * i) // mi >= 0:
			x = i
			y = (n - ma * i) // mi
			t = 0
			break
	if t:
		print(-1)
	else:
		ind = 0
		for i in range(x):
			for j in range(ma * i + 1, ma * (i + 1) + 1):
				if j > 1000000:
					print(j)
				ab[j] = j + 1
				if j % ma == 0:
					ab[j] = j - ma + 1
		k = ma * x
		for i in range(y):
			for j in range(mi * i + 1, mi * (i + 1) + 1):
				ab[k + j] = k + j + 1
				if j % mi == 0:
					ab[k + j] = k + j - mi + 1
		print(*ab[1:])


(n, a, b) = map(int, input().strip().split())

def pp(seq):
	return ' '.join(map(str, seq))

def cycle(start, size):
	return list(range(start + 1, start + size)) + [start]

def fail_sequence(target, acc=[]):
	if target % a == 0:
		return acc + [a] * (target // a)
	if target % b == 0:
		return acc + [b] * (target // b)
	if a <= target:
		acc.append(a)
		res = sequence(target - a, acc)
		if res:
			return res
		acc.pop()
	if b <= target:
		acc.append(b)
		return sequence(target - b, acc)
	return []

def sequence(target, a, b):
	dp = {0: (0, 0)}
	for i in range(1, target + 1):
		if i - a in dp:
			(na, nb) = dp[i - a]
			dp[i] = (na + 1, nb)
		elif i - b in dp:
			(na, nb) = dp[i - b]
			dp[i] = (na, nb + 1)
	(na, nb) = dp.get(target, (0, 0))
	return [a] * na + [b] * nb

def sol():
	seq = sequence(n, a, b)
	if seq:
		res = []
		i = 1
		for size in seq:
			res.extend(cycle(i, size))
			i += size
		return pp(res)
	else:
		return -1
print(sol())


import sys
(n, a, b) = list(map(int, sys.stdin.readline().strip().split()))

def euc(a, b):
	if b > a:
		(d, p, q) = euc(b, a)
		return (d, q, p)
	if b == 0:
		return (a, 1, 0)
	s = a // b
	(d, sp, sq) = euc(a - s * b, b)
	return (d, sp, sq - s * sp)

def normalize(n, a, b, d, p, q):
	if p < 0:
		(sp, sq) = normalize(n, b, a, d, q, p)
		return (sq, sp)
	elif q >= 0:
		return (p, q)
	r = -(q // (a // d))
	sp = p - r * (b // d)
	sq = q + r * (a // d)
	if sp < 0:
		raise ValueError
	else:
		return (sp, sq)
(d, p, q) = euc(a, b)
if n % d != 0:
	print('-1')
	return
m = n // d
(p, q) = (m * p, m * q)
try:
	(p, q) = normalize(n, a, b, d, p, q)
except ValueError:
	print('-1')
	return
res = []
last = 1
for _ in range(p):
	res.extend(list(range(last + 1, last + a)))
	res.append(last)
	last += a
for _ in range(q):
	res.extend(list(range(last + 1, last + b)))
	res.append(last)
	last += b
print(' '.join(map(str, res)))


(n, a, b) = list(map(int, input().split()))
choose = None
for i in range(n + 1):
	if a * i > n:
		continue
	j = (n - a * i) // b
	if i * a + j * b == n:
		choose = (i, j)
if choose:
	(i, j) = choose
	arr = []
	for t in range(i):
		arr.append(a)
	for t in range(j):
		arr.append(b)
	got = 0
	answer = []
	for x in arr:
		cur = []
		for i in range(got + 1, got + x + 1):
			cur.append(i)
		cur = cur[1:] + [cur[0]]
		got += x
		answer += cur
	print(' '.join(map(str, answer)))
else:
	print(-1)


ans = []

def go(base, n):
	ans.append(base + n - 1)
	for i in range(base, base + n - 1):
		ans.append(i)

def solve(n, a, b, x):
	cur_start = 1
	y = (n - a * x) // b
	for i in range(x):
		go(cur_start, a)
		cur_start += a
	for i in range(y):
		go(cur_start, b)
		cur_start += b
(n, a, b) = map(int, input().split())
for x in range(0, 10 ** 6 + 1):
	if (n - x * a) % b == 0 and n - x * a >= 0:
		solve(n, a, b, x)
		print(' '.join(map(str, ans)))
		break
else:
	print(-1)


(n, a, b) = map(int, input().split())
cop = n
if a > b:
	(a, b) = (b, a)
j = -1
ke = -1
while n >= 0:
	if n % a == 0:
		j = n // a
		ke = (cop - a * j) // b
		break
	else:
		n -= b
if j == -1:
	print(-1)
else:
	ans = []
	t = 1
	for yu in range(j):
		for ty in range(a):
			k = t + (ty + 1) % a
			if k == 0:
				k += a
			ans.append(k)
		t += a
	for yu in range(ke):
		for ty in range(b):
			k = t + (ty + 1) % b
			if k == 0:
				k += b
			ans.append(k)
		t += b
	print(*ans, sep=' ')


(n, a, b) = [int(x) for x in input().split()]

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
(g, a_1, b_1) = egcd(a, b)
if n % g:
	print(-1)
	return
fac = n // g
a_1 *= fac
b_1 *= fac
if a_1 < 0:
	while a_1 < 0:
		a_1 += b // g
		b_1 -= a // g
	if b_1 < 0:
		print(-1)
		return
elif b_1 < 0:
	while b_1 < 0:
		b_1 += a // g
		a_1 -= b // g
	if a_1 < 0:
		print(-1)
		return
res = []
i = 1
for _ in range(a_1):
	for j in range(a - 1):
		i += 1
		res.append(i)
	res.append(i - a + 1)
	i += 1
for _ in range(b_1):
	for j in range(b - 1):
		i += 1
		res.append(i)
	res.append(i - b + 1)
	i += 1
print(' '.join(map(str, res)))


def exgcd(a, b):
	if b > 0:
		(y, x, g) = exgcd(b, a % b)
		y -= a // b * x
		return (x, y, g)
	else:
		return (1, 0, a)
(n, a, b) = map(int, input().split())
(x0, y0, g) = exgcd(a, b)
if n % g != 0:
	print(-1)
	return
a //= g
b //= g
k = n // g
r = k * x0 // b
l = (k * -y0 + a - 1) // a
if l > r:
	print(-1)
	return
x = k * x0 - b * l
y = k * y0 + a * l
a *= g
b *= g
for i in range(x):
	for j in range(a - 1):
		print(i * a + j + 2, end=' ')
	print(i * a + 1, end=' ')
for i in range(y):
	for j in range(b - 1):
		print(x * a + i * b + j + 2, end=' ')
	print(x * a + i * b + 1, end=' ')
print()


(n, a, b) = map(int, input().split())
p = [i + 1 for i in range(n)]
f = 0
(a, b) = (min(a, b), max(a, b))
for i in range(0, n + 1, a):
	if (n - i) % b == 0:
		x = (n - i) // b
		f = 1
		break
if f:
	for i in range(0, b * x, b):
		p[i:i + b] = [p[i + b - 1]] + p[i:i + b - 1]
	for j in range(b * x, n, a):
		p[j:j + a] = [p[j + a - 1]] + p[j:j + a - 1]
	print(*p)
else:
	print(-1)


res = []

def solve(Ax, A, sum=0):
	for i in range(0, Ax):
		for k in range(0, A):
			if k == 0:
				res.append(sum + A)
			else:
				res.append(sum + k)
		sum += A
	return sum
s = input().split()
N = int(s[0])
A = int(s[1])
B = int(s[2])
Ax = Bx = 0
while 1:
	if Ax * A > N:
		break
	Bx = N - Ax * A
	if Bx % B == 0:
		Bx //= B
		break
	Ax += 1
if Ax * A + Bx * B != N:
	print('-1')
else:
	solve(Bx, B, solve(Ax, A))
	print(' '.join(map(str, res)))


(n, a, b) = (int(x) for x in input().split())
l = -1
for k in range(n // a + 1):
	if (n - k * a) % b == 0:
		l = (n - k * a) // b
		break
if l == -1:
	print(-1)
	quit()
perm = []
curr_last_op = 1
for i in range(k):
	curr_cycle = [curr_last_op + j for j in range(a)]
	curr_last_op = curr_last_op + a
	perm += curr_cycle[1:] + curr_cycle[:1]
for i in range(l):
	curr_cycle = [curr_last_op + j for j in range(b)]
	curr_last_op = curr_last_op + b
	perm += curr_cycle[1:] + curr_cycle[:1]
print(*perm)


def solution(a, b, n):
	i = 0
	while i * a <= n:
		if (n - i * a) % b == 0:
			return (i, int((n - i * a) / b))
		i = i + 1
	return -1
(n, a, b) = map(int, input().split())
(a, b) = (max(a, b), min(a, b))
x = solution(a, b, n)
if x == -1:
	print(x)
else:
	ans = []
	(r, s) = (x[0], x[1])
	curr = 1
	while r:
		last = a + curr - 1
		ans.append(last)
		for i in range(curr, curr + a - 1):
			ans.append(i)
		curr += a
		r -= 1
	while s:
		last = b + curr - 1
		ans.append(last)
		for i in range(curr, curr + b - 1):
			ans.append(i)
		curr += b
		s -= 1
	print(*ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, a, b) = map(int, input().split())
(x, y) = (0, 0)
ok = False
for i in range(n // a + 1):
	if (n - a * i) % b == 0:
		ok = True
		(x, y) = (i, (n - a * i) // b)
		break
if not ok:
	print(-1)
	exit()
pos = 1
for i in range(x):
	print(pos + a - 1, end=' ')
	for j in range(a - 1):
		print(pos + j, end=' ')
	pos += a
for i in range(y):
	print(pos + b - 1, end=' ')
	for j in range(b - 1):
		print(pos + j, end=' ')
	pos += b


from sys import stdin, stdout
from random import randrange
(n, a, b) = map(int, stdin.readline().split())
(first, second) = (-1, -1)
for i in range(n):
	if a * i > n:
		break
	if not (n - a * i) % b:
		(first, second) = (i, (n - a * i) // b)
		break
if min(first, second) == -1:
	stdout.write('-1')
else:
	ans = [0 for i in range(n + 1)]
	current = 1
	for i in range(first):
		ans[current] = current + a - 1
		current += 1
		for j in range(1, a):
			ans[current] = current - 1
			current += 1
	for i in range(second):
		ans[current] = current + b - 1
		current += 1
		for j in range(1, b):
			ans[current] = current - 1
			current += 1
	stdout.write(' '.join(list(map(str, ans[1:]))))


(n, a, b) = map(int, input().split())
(x, y) = (0, 0)
ok = False
for i in range(n // a + 1):
	if (n - a * i) % b == 0:
		ok = True
		(x, y) = (i, (n - a * i) // b)
		break
if not ok:
	print(-1)
	exit()
pos = 1
for i in range(x):
	print(pos + a - 1, end=' ')
	for j in range(a - 1):
		print(pos + j, end=' ')
	pos += a
for i in range(y):
	print(pos + b - 1, end=' ')
	for j in range(b - 1):
		print(pos + j, end=' ')
	pos += b


(n, a, b) = map(int, input().split())
for i in range(n // a + 1):
	if (n - i * a) % b == 0:
		res = []
		for j in range(i):
			t = [j * a + k for k in range(1, a + 1)]
			res += t[1:] + [t[0]]
		for j in range((n - i * a) // b):
			t = [i * a + j * b + k for k in range(1, b + 1)]
			res += t[1:] + [t[0]]
		print(*res)
		break
else:
	print(-1)


(n, a, b) = map(int, input().split())
(x, y) = (-1, -1)
for i in range(n + 1):
	if n - a * i >= 0 and (n - a * i) % b == 0:
		x = i
		y = (n - a * i) // b
		break
if x == -1:
	print(-1)
	exit()
ans = [-1] * n
for i in range(0, a * x, a):
	for j in range(i, i + a - 1):
		ans[j] = j + 1
	ans[i + a - 1] = i
for i in range(a * x, n, b):
	for j in range(i, i + b - 1):
		ans[j] = j + 1
	ans[i + b - 1] = i
for i in range(n):
	ans[i] += 1
print(*ans)


(N, A, B) = map(int, input().split())
for i in range(N // A + 1):
	if (N - i * A) % B == 0:
		ans = []
		for j in range(i):
			l = []
			for k in range(1, A + 1):
				l.append(j * A + k)
			ans += l[1:] + [l[0]]
		for j in range((N - i * A) // B):
			l = []
			for k in range(1, B + 1):
				l.append(i * A + j * B + k)
			ans += l[1:] + [l[0]]
		print(*ans)
		break
else:
	print(-1)


def solve(a, b, n):
	i = 0
	while i * a <= n:
		if (n - i * a) % b == 0:
			x = i
			y = (n - i * a) // b
			return (x, y)
		i = i + 1
	return (-1, -1)
(n, a, b) = map(int, input().split())
(aa, bb) = solve(a, b, n)
l = []
if (aa, bb) == (-1, -1):
	print(-1)
else:
	for i in range(1, aa + 1):
		x = a * (i - 1) + 1
		y = a * i
		l += [y]
		l += [j for j in range(x, y)]
	for i in range(1, bb + 1):
		x = a * aa + b * (i - 1) + 1
		y = a * aa + b * i
		l += [y]
		l += [j for j in range(x, y)]
	print(' '.join(map(str, l)))


def main():
	(n, a, b) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	s = []
	k = 1
	ok = False
	x = 0
	y = 0
	for j in range(n):
		kk = n - a * j
		if kk >= 0:
			if kk % b == 0:
				ok = True
				x = j
				y = kk // b
				break
	if not ok:
		print(-1)
		return
	for j in range(x):
		for i in range(a - 1):
			s.append(k + i + 1)
		s.append(k)
		k += a
		n -= a
	for j in range(y):
		for i in range(b - 1):
			s.append(k + i + 1)
		s.append(k)
		k += b
		n -= b
	print(*s)
	return
main()


(n, a, b) = map(int, input().split())
r = []

def f(a, l, r=r):
	r += [a + l - 1] + list(range(a, a + l - 1))
i = 1
while n > 0:
	if n % b is 0:
		break
	f(i, a)
	i += a
	n -= a
while n > 0:
	f(i, b)
	i += b
	n -= b
print(-1) if n else print(*r)


def main():
	(n, a, b) = map(int, input().split())
	found = False
	for x in range(n + 1):
		rem = n - a * x
		if rem >= 0 and rem % b == 0:
			y = rem // b
			found = True
			break
	if not found:
		print(-1)
		return
	ans = []
	if a == 1 or b == 1:
		for i in range(n):
			ans.append(i + 1)
	else:
		start = 1
		for i in range(x):
			arr = [start + 1]
			for j in range(a - 2):
				arr.append(arr[-1] + 1)
			arr.append(start)
			start = arr[-2] + 1
			ans.extend(arr)
		for i in range(y):
			arr = [start + 1]
			for j in range(b - 2):
				arr.append(arr[-1] + 1)
			arr.append(start)
			start = arr[-2] + 1
			ans.extend(arr)
	for i in ans:
		print(i, end=' ')
main()