/ 
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 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 進法表記が用いられます．
数列の辞書順とは？
数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います．ここで，|A|, |B| はそれぞれ A, B の長さを表します．
- |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
- ある整数 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
Score : 900 points
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.
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