問題文

$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|<|B|$ かつ $(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 < B_i$.

制約

• $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$ 進法表記を用いてください．

---

入力例 1

3 1 9 1 9

出力例 1

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

---

入力例 2

3 2 9 1 9

出力例 2

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

3 2 9 3 8

出力例 3

3
4
6
9
7
8

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

---

入力例 4

10 9 1000000000000000000 123456789123456789 123456789123456799

出力例 4

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909