配点 : $900$ 点

問題文

$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$ 進法表記が用いられます．

制約

• $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$

入力

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

$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

$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).

3 2 9 1 9

1
2
3
4
6
9
7
8
5

$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$ から分かります．

3 2 9 3 8

3
4
6
9
7
8

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

10 9 1000000000000000000 123456789123456789 123456789123456799

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909