← 返回题目列表

Codeforces · 460/D

D. 小维克多和套装

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

小维克多喜欢集合论。让我们提醒您,集合是一组数字,其中所有数字都是成对不同的。今天 Victor 想要找到一组具有以下属性的整数 S:

- 对于所有 x $$( x \in S )$$,以下不等式成立 l ≤ x ≤ r;
- 1 ≤ |S| ≤ k;
- 让我们将集合 S 的第 i 个元素表示为 si;值 $$f(S) = s_1 \oplus s_2 \oplus \cdots \oplus s_{|S|}$$ 必须尽可能小。

帮助 Victor 找到所描述的集合。

输入

第一行包含三个空格分隔的整数 l、r、k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1))。

输出

打印 f(S) 的最小可能值。然后打印集合|S|的基数。然后以任意顺序打印集合的元素。

如果有多个最佳设置,您可以打印其中任何一个。

示例

输入 #1

8 15 3

输出 #1

1
2
10 11

输入 #2

8 30 7

输出 #2

0
5
14 9 28 11 16

注意

运算$$x \oplus y$$ 表示按位异或运算。换句话说,就是异或运算。