问题陈述

令 $r > 1$ 为一个有理数，$p$ 和 $q$ 分别为 $r$ 的分子和分母。也就是说，$p$ 和 $q$ 是满足 $r = \frac{p}{q}$ 且 $\gcd(p,q) = 1$ 的正整数。

将正整数 $n$ 的 基数为 $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}$。

考虑按照它们的基数为 $\frac{p}{q}$ 的展开以字典顺序升序排列所有不大于 $N$ 的正整数。找出这个列表中的第 $L$ 个、第 $(L+1)$ 个、$\ldots$、第 $R$ 个正整数。

按照惯例，输入和输出正整数采用十进制表示。

什么是序列的字典顺序？

一个序列 $A = (A_1, \ldots, A_{|A|})$ 满足以下条件时，被称为字典上更小于序列 $B = (B_1, \ldots, B_{|B|})$。这里，$|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|\}$ 使得以下两个条件都满足。
   • $(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$ 行应该包含所有正整数列表中第 $(L + i - 1)$ 个正整数，按照它们的基数为 $\frac{p}{q}$ 的展开以字典顺序升序排列。

使用十进制表示打印正整数。

---

示例输入 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).

例如，可以从 $2\cdot \left(\frac32\right)^2 + 1\cdot \frac32 + 0\cdot 1 = 6$ 看出正整数 $6$ 的基数为 $\frac32$ 的展开是 $(2,1,0)$。

---

示例输入 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