/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
整数列 P = (P_1, \ldots, P_M) に対して、各 1\leq i\leq M-1 に対して P_i と P_{i+1} の間に P_i + P_{i+1} を挿入することで得られる数列を f(P) と書くことにします。より形式的には次の通りです：
- 1\leq i\leq M - 1 に対して Q_i = P_i + P_{i+1} とする。
- 2M-1 項からなる数列 f(P) を f(P) = (P_1, Q_1, P_2, Q_2, \ldots, P_{M-1}, Q_{M-1}, P_M) により定める。
正の整数 a, b, N（ただし a, b\leq N）が与えられます。数列 A = (a, b) から始めて、以下の手順によって数列 B = (B_1, B_2, \ldots) を定めます。
- A を f(A) に取り換えることを、N 回繰り返す。
- その後、数列 A から N より大きな値を取り除いてできる数列を、数列 B とする。
B_L, \ldots, B_R を求めてください。
制約
- 1\leq N\leq 3\times 10^5
- 1\leq a, b\leq N
- 1\leq L\leq R\leq 10^{18}
- R - L < 3\times 10^5
- R は数列 B の項数以下である
入力
入力は以下の形式で標準入力から与えられます。
a b N L R
出力
B_L, \ldots, B_R を空白区切りで 1 行で出力してください。
入力例 1
1 1 4 1 7
出力例 1
1 4 3 2 3 4 1
はじめ A = (1, 1) です。A を f(A) を取り換える操作により、数列 A は以下のように変化します：
- 1 回目の操作：A = (1, 2, 1)
- 2 回目の操作：A = (1, 3, 2, 3, 1)
- 3 回目の操作：A = (1, 4, 3, 5, 2, 5, 3, 4, 1)
- 4 回目の操作：A = (1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1)
したがって B = (1, 4, 3, 2, 3, 4, 1) となります。この数列の第 1 項目から第 7 項目までが答えとなります。
入力例 2
1 1 4 2 5
出力例 2
4 3 2 3
この入力例でも、B = (1, 4, 3, 2, 3, 4, 1) となります。この数列の第 2 項目から第 5 項目までが答えとなります。
入力例 3
2 1 10 5 15
出力例 3
8 3 10 7 4 9 5 6 7 8 9
入力例 4
10 10 10 2 2
出力例 4
10
Score : 1000 points
Problem Statement
For a sequence of integers P = (P_1, \ldots, P_M), let f(P) denote the sequence obtained by inserting P_i + P_{i+1} between P_i and P_{i+1} for each 1\leq i\leq M-1. More formally:
- Let Q_i = P_i + P_{i+1} for each 1\leq i\leq M - 1.
- Let f(P) be defined as a sequence of 2M-1 integers f(P) = (P_1, Q_1, P_2, Q_2, \ldots, P_{M-1}, Q_{M-1}, P_M).
Given are three positive integers a, b, and N where a, b\leq N. Let us begin with a sequence A = (a, b) and define a sequence B = (B_1, B_2, \ldots) as follows.
- Do the following N times: replace A with f(A).
- Then, remove from A all values greater than N and let B be the resulting sequence.
Find B_L, \ldots, B_R.
Constraints
- 1\leq N\leq 3\times 10^5
- 1\leq a, b\leq N
- 1\leq L\leq R\leq 10^{18}
- R - L < 3\times 10^5
- R is at most the number of elements in the sequence B.
Input
Input is given from Standard Input in the following format:
a b N L R
Output
Print a line containing B_L, \ldots, B_R, with a space in between.
Sample Input 1
1 1 4 1 7
Sample Output 1
1 4 3 2 3 4 1
Initially, A = (1, 1). The replacements of A with f(A) take place as follows.
- After the first replacement: A = (1, 2, 1).
- After the second replacement: A = (1, 3, 2, 3, 1).
- After the third replacement: A = (1, 4, 3, 5, 2, 5, 3, 4, 1).
- After the fourth replacement: A = (1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1).
Thus, we have B = (1, 4, 3, 2, 3, 4, 1). We should report the 1-st through 7-th elements of this sequence.
Sample Input 2
1 1 4 2 5
Sample Output 2
4 3 2 3
Again, we have B = (1, 4, 3, 2, 3, 4, 1). We should report the 2-nd through 5-th elements of this sequence.
Sample Input 3
2 1 10 5 15
Sample Output 3
8 3 10 7 4 9 5 6 7 8 9
Sample Input 4
10 10 10 2 2
Sample Output 4
10