小维克多喜欢集合论。让我们提醒您,集合是一组数字,其中所有数字都是成对不同的。今天 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$$ 表示按位异或运算。换句话说,就是异或运算。