分数: 1000 点
问题陈述
对于整数序列 P = (P_1, \ldots, 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, \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) 如下。
- 执行以下操作 N 次:更换 A 与 f(A).
- 然后,从 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
1 4 3 2 3 4 1
最初, A = (1, 1)。的替代品 A 与 f(A) 发生如下。
- 第一次替换后: A = (1, 2, 1).
- 第二次更换后: A = (1, 3, 2, 3, 1).
- 第三次替换后: A = (1, 4, 3, 5, 2, 5, 3, 4, 1).
- 第四次替换后: 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-st 通过 7该序列的第一个元素。
示例输入 2
1 1 4 2 5
示例输出 2
4 3 2 3
再次,我们有 B = (1, 4, 3, 2, 3, 4, 1)。我们应该报告 2-nd 通过 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