← 返回题目列表

AtCoder · arc123_f

F. 插入添加

中文机器翻译题面 查看原题

分数: 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