题目描述

$r\ >\ 1$ を有理数とし，$p$ を $r$ の分子，$q$ を $r$ の分母とします．つまり $p,\ q$ は正整数で $r\ =\ \frac{p}{q}$ かつ $\gcd(p,q)\ =\ 1$ が成り立つとします．

正整数 $n$ の $\boldsymbol{r}$ 進法展開 を，次の条件をすべて満たす整数列 $(a_1,\ \ldots,\ a_k)$ のことと定義します．

• $a_i$ は $0$ 以上 $p-1$ 以下の整数
• $a_1\neq\ 0$
• $n\ =\ \sum_{i=1}^k\ a_ir^{k-i}$

任意の正整数 $n$ が唯一の $r$ 進法展開を持つことが証明できます．

正整数 $p,\ q,\ N,\ L,\ R$ が与えられます．ここで，$p,\ q$ は $1.01\ \leq\ \frac{p}{q}$ を満たします．

$N$ 以下の正整数全体を，$\frac{p}{q}$ 進法展開の辞書順が小さい方から順に並べたとき，$L,\ L+1,\ \ldots,\ R$ 番目に並ぶ正整数を答えてください．

なお，正整数の入出力には通常の $10$ 進法表記が用いられます．

数列の辞書順とは？ 数列 $A\ =\ (A_1,\ \ldots,\ A_{|A|})$ が $B\ =\ (B_1,\ \ldots,\ B_{|B|})$ より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います．ここで，$|A|$, $|B|$ はそれぞれ $A$, $B$ の長さを表します．

1. $ |A|\ かつ\ (A_{1},\ldots,A_{|A|})\ =\ (B_1,\ldots,B_{|A|}) $.
2. ある整数 $1\leq\ i\leq\ \min\{|A|,|B|\}$ が存在して，下記の $2$ つがともに成り立つ．

• $(A_{1},\ldots,A_{i-1})\ =\ (B_1,\ldots,B_{i-1})$.
• $A_i\ .$

输入格式

入力は以下の形式で標準入力から与えられます．

$p$ $q$ $N$ $L$ $R$

输出格式

$R-L+1$ 行出力してください．$i$ 行目には，$N$ 以下の正整数全体を，$\frac{p}{q}$ 進法展開の辞書順が小さい方から順に並べたとき，$L\ +\ i\ -\ 1$ 番目に並ぶ正整数を出力してください．

正整数の出力には $10$ 進法表記を用いてください．

3 1 9 1 9

1
3
9
4
5
2
6
7
8

3 2 9 1 9

1
2
3
4
6
9
7
8
5

3 2 9 3 8

3
4
6
9
7
8

10 9 1000000000000000000 123456789123456789 123456789123456799

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909

提示

制約

• $1\leq\ p,\ q\ \leq\ 10^9$
• $\gcd(p,q)\ =\ 1$
• $1.01\ \leq\ \frac{p}{q}$
• $1\leq\ N\leq\ 10^{18}$
• $1\leq\ L\leq\ R\leq\ N$
• $R\ -\ L\ +\ 1\leq\ 3\times\ 10^5$

Sample Explanation 1

$9$ 以下の正整数の $3$ 進法展開は次の通りです． 1: (1), 2: (2), 3: (1, 0), 4: (1, 1), 5: (1, 2), 6: (2, 0), 7: (2, 1), 8: (2, 2), 9: (1, 0, 0).

Sample Explanation 2

$9$ 以下の正整数の $\frac32$ 進法展開は次の通りです． 1: (1), 2: (2), 3: (2, 0), 4: (2, 1), 5: (2, 2), 6: (2, 1, 0), 7: (2, 1, 1), 8: (2, 1, 2), 9: (2, 1, 0, 0). 例えば $6$ の $\frac32$ 進法展開が $(2,1,0)$ であることは，$ 2\cdot\ \bigl(\frac32\bigr)^2\ +\ 1\cdot\ \frac32\ +\ 0\cdot\ 1\ =\ 6 $ から分かります．

Sample Explanation 3

入力例 2 の出力のうち $3$ 番目から $8$ 番目が答となります．