Description

Momo really likes finding patterns and filling in numbers. For example, $1,4,7,( ),\cdots$: the difference between adjacent numbers is $3$, so the number in the parentheses should be $10$. Another example is $3,6,12,( ),\cdots$: each number is twice the previous one, so the number in the parentheses should be $24$.

After playing this kind of game for many years, Momo got tired of arithmetic sequences and geometric sequences. When she sees the sequence $1,2,\cdots,n$, she wants to change its order as little as possible so that there is no subsequence with common difference $A$ or common ratio $B$.

More specifically, given integers $n,A,B$, find a permutation $P=(P_1,P_2,\cdots,P_n)$ of $1$ to $n$ such that $\forall i,j \in \{1,2,\cdots,n\}$, if $i<j$ and $P_i<P_j$, then $P_j \neq P_i+A$ and $P_j \neq P_i \times B$. The degree to which the permutation $P$ keeps the original order is defined as $S$:

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

Under the above constraints, please make the value of $S$ as large as possible.

Input Format

The first line contains three positive integers $n,A,B$, with meanings as described above. Adjacent numbers are separated by one space.

Output Format

The first line contains $n$ integers, the permutation $P$ you found. Adjacent numbers are separated by spaces.

4 3 2

4 2 1 3

Hint

Sample Explanation

For this permutation, $S = 3$, which is the maximum possible $S$ when $n=4,A=3,B=2$.

---

Scoring

Each test point is scored independently.

For each test point, if your output is invalid, such as wrong file format, or the output solution does not satisfy the requirements, then you get $0$ points for that test point.

Otherwise, let the $S$ value of your permutation be $a$, and the $S$ value of the permutation we provide be $b$. Your score for that test point is:

• If $a \le b$, you get $10$ points.
• Otherwise, the score is:

$\max \{ [10 \times ( \exp (\frac{a}{b}-2)],1 \}$

---

Constraints

There are $10$ test points in total. The constraints are:

Test Point ID	$n$	$A$	$B$
$1$	$\le 30$	$\le n$
$2$	$\le 60$	$A\bmod B\not =0$	$\ge 4$
$3$	$\le 70$		$\ge 5$
$4$	$\le 80$		$\ge 6$
$5$	$\le 90$		$\ge 7$
$6$		$\le n$	$=1$
$7,8$		$\le 5$	$\le n$
$9$	$=60$	$=21$	$=3$
$10$	$=90$	$=18$	$=2$

In all input data, both $A$ and $B$ are positive integers not exceeding $n$.

Translated by ChatGPT 5