[ARC123F] Insert Addition

对于一个有 $M$ 个元素的整数序列 $P=(P_1,...,P_M)$ ，定义 $f(P)$ 为：在原序列中，向每个 $P_i$ 和 $P_{i+1}$ 之间插入一个值为 $P_i+P_{i+1}$ 的元素（$1\leq i\leq M-1$）得到的序列。 更形式化的： + $Q_i=P_i+P_{i+1},1\leq i\leq M-1$. + $f(P)$ 是一个由 $2M-1$ 个整数组成的序列：$f(P)=(P_1,Q_1,P_2,Q_2,\cdots,P_{M-1},Q_{M-1},P_M)$. 现给定三个正整数 $a,b,N$（$a,b\leq N$）。开始时序列 $A=(a,b)$。 接下来，进行 $N$ 次如下操作：将 $A$ 变为 $f(A)$ 。 最后，将序列 $A$ 中所有大于 $N$ 的数删去，得到最终的序列 $B$。 给定 $L,R$ ，输出 $B_L,\cdots,B_R$ 。

[problemUrl]: https://atcoder.jp/contests/arc123/tasks/arc123_f 整数列 $ 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 $ を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ a $ $ b $ $ N $ $ L $ $ R $

$ B_L,\ \ldots,\ B_R $ を空白区切りで $ 1 $ 行で出力してください。

1 1 4
1 7

1 4 3 2 3 4 1

1 1 4
2 5

4 3 2 3

2 1 10
5 15

8 3 10 7 4 9 5 6 7 8 9

10 10 10
2 2

10

### 制約 - $ 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 $ の項数以下である ### Sample Explanation 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 $ 項目までが答えとなります。 ### Sample Explanation 2 この入力例でも、$ B\ =\ (1,\ 4,\ 3,\ 2,\ 3,\ 4,\ 1) $ となります。この数列の第 $ 2 $ 項目から第 $ 5 $ 項目までが答えとなります。