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.

1. $|A|<|B|$ and $(A_{1},\\ldots,A_{|A|}) = (B_1,\\ldots,B_{|A|})$.
2. 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$.

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$

---

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.

---

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