配点 : $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 4
1 7

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$ 項目までが答えとなります。

1 1 4
2 5

4 3 2 3

この入力例でも、$B = (1, 4, 3, 2, 3, 4, 1)$ となります。この数列の第 $2$ 項目から第 $5$ 項目までが答えとなります。

2 1 10
5 15

8 3 10 7 4 9 5 6 7 8 9

10 10 10
2 2

10