Problem Statement

Let r > 1 be a rational number, and p and q be the numerator and denominator of r, respectively. That is, p and q are positive integers such that $r = \frac{p}{q}$ and $\gcd(p,q) = 1$.
Let the $base-\boldsymbol{r}$ expansion of a positive integer n be the integer sequence $(a_1, \ldots, a_k)$ that satisfies all of the following conditions.

• a_i is an integer between 0 and p-1.
• $a_1\neq 0$.
• $n = \sum_{i=1}^k a_ir^{k-i}$.

It can be proved that any positive integer n has a unique base-r expansion.

You are given positive integers p, q, N, L, and R. Here, p and $q satisfy 1.01 \leq \frac{p}{q}$.
Consider sorting all positive integers not greater than N in ascending lexicographical order of their $base-\frac{p}{q}$ expansions. Find the $L-th, (L+1)-th, \ldots, R-th$ positive integers in this list.
As usual, decimal notations are used in the input and output of positive integers.
What is lexicographical order on sequences?

$A sequence A = (A_1, \ldots, A_{|A|})$ is said to be lexicographically smaller than $B = (B_1, \ldots, B_{|B|})$ when 1. or 2. below is satisfied. Here, |A| and |B| denote the lengths of A and B, respectively.

• |A|<|B| and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$.

• There is an integer $1\leq i\leq \min${|A|,|B|} that satisfies both of the following.

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

• A_i < B_i.

Input

The input is given from Standard Input in the following format:
p q N L R

Output

Print R-L+1 lines. The i-th line should contain the (L + i - 1)-th positive integer in the list of all positive integers not greater than N sorted in ascending lexicographical order of their $base-\frac{p}{q}$ expansions.
Use decimal notations to print positive integers.

Constraints

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

3 1 9 1 9

Sample Output 1

1
3
9
4
5
2
6
7
8

The base-3 expansions of the positive integers not greater than 9 are as follows.
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 Input 2

3 2 9 1 9

Sample Output 2

1
2
3
4
6
9
7
8
5

The $base-\frac32$ expansions of the positive integers not greater than 9 are as follows.
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).

One can see that the $base-\frac32$ expansion of 6 is (2,1,0), for instance, from $2\cdot \bigl(\frac32\bigr)^2 + 1\cdot \frac32 + 0\cdot 1 = 6$.

Sample Input 3

3 2 9 3 8

Sample Output 3

3
4
6
9
7
8

This is the 3-rd through 8-th lines of the output to Sample Input 2.

Sample Input 4

10 9 1000000000000000000 123456789123456789 123456789123456799

Sample Output 4

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909

见题面 Input 部分

见题面 Output 部分