Permutation with Forbidden Differences and Multiplications

MoMo loves finding patterns in numbers. For example, in the sequence $$1,4,7,(\ ),\cdots$$ the adjacent difference is $$3$$, so the missing number is $$10$$; in the sequence $$3,6,12,(\ ),\cdots$$ every term is twice the previous one, so the missing number is $$24$$.

Tired of simple arithmetic and geometric progressions, MoMo now considers the permutation of numbers from $$1$$ to $$n$$. She wants to rearrange the sequence as little as possible while ensuring that for any two indices $$i,j$$ (with $$1\le i < j \le n$$) for which $$P_i < P_j$$, it is not the case that

• $$P_j = P_i + A$$, or
• $$P_j = P_i \times B$$.

Let the preserved order measure be defined by

$$S = \sum_{1 \le i \le j \le n,\ P_i<P_j} (P_j-P_i). $$

Your task is: given integers $$n, A, B$$, output a permutation $$P=(P_1,P_2,\cdots,P_n)$$ of the numbers $$1,2,\cdots,n$$ that meets the above forbidden-subsequence conditions, and among all valid permutations, one that maximizes $$S$$ (i.e. preserves the natural order as much as possible).

Note: If a pair of elements would naturally appear in increasing order (and contribute to a large $$S$$), you should maintain that order unless it violates any of the conditions. In particular, for every $$x$$ such that $$x+A\le n$$, the numbers $$x$$ and $$x+A$$ cannot appear in increasing order, and for every $$x$$ with $$x\times B\le n$$, the numbers $$x$$ and $$x\times B$$ cannot appear in increasing order.

A way to view the problem is to build a directed graph where for each $$x$$ with $$x+A\le n$$, add an edge from $$x+A$$ to $$x$$ (forcing $$x+A$$ to appear before $$x$$), and similarly for each $$x$$ with $$x\times B\le n$$, add an edge from $$x\times B$$ to $$x$$. Then, a valid permutation is a linear extension of this partial order. Among all linear extensions, you are to find one as close to the natural ascending order as possible.

inputFormat

The input consists of one line containing three integers $$n, A, B$$.

outputFormat

Output a valid permutation of the numbers from $$1$$ to $$n$$ in one line, separated by spaces.

sample

5 1 2

5 4 3 2 1