题目描述

对于整数列 $P = (P_1, \ldots, P_M)$，我们定义操作 $f(P)$ 为：对于每个 $1 \leq i \leq M-1$，在 $P_i$ 和 $P_{i+1}$ 之间插入 $P_i + P_{i+1}$。更形式化地，定义如下：

• 对于 $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

样例 2

输入

1 1 4
2 5

输出

4 3 2 3

样例 3

输入

2 1 10
5 15

输出

8 3 10 7 4 9 5 6 7 8 9

样例 4

输入

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$ 的长度

样例解释 1

初始时 $A = (1, 1)$。经过 $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

本样例下，$B = (1, 4, 3, 2, 3, 4, 1)$。本题要求输出该数列的第 $2$ 项到第 $5$ 项。

由 ChatGPT 4.1 翻译