Problem: Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:

  * for all x <image> the following inequality holds l ≤ x ≤ r; 
  * 1 ≤ |S| ≤ k; 
  * lets denote the i-th element of the set S as si; value <image> must be as small as possible. 



Help Victor find the described set.

Input

The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).

Output

Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.

If there are multiple optimal sets, you can print any of them.

Examples

Input

8 15 3


Output

1
2
10 11


Input

8 30 7


Output

0
5
14 9 28 11 16

Note

Operation <image> represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

Solution (in PYTHON):

Solution:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import sys

l, r, k = map(int, raw_input().strip().split())
length = r - l + 1

if k == 1:
    print '\n'.join([str(l), '1', str(l)])
elif k == 2:
    res = None
    if length > 2 or l % 2 == 0: res = ['1', '2', ' '.join([str(l), str(l + 1)] if l % 2 == 0 else [str(l + 1), str(l + 2)])]
    else: res = [str(l), '1', str(l)] if l < l ^ r else [str(l ^ r), '2', ' '.join([str(l), str(r)])]
    print '\n'.join(res)
elif k == 3:
    x, y, z, res = 1, 2, 3, None
    while x < l:
        x = (x << 1) + 1
        y = (y << 1) + 1
        z = z << 1
    if z <= r: res = ['0', '3', ' '.join([str(x), str(y), str(z)])]
    else: res = ['1', '2', ' '.join([str(l), str(l + 1)] if l % 2 == 0 else [str(l + 1), str(l + 2)])]
    print '\n'.join(res)
elif k == 4:
    res = None
    if length > 4 or l % 2 == 0: res = ['0', '4', ' '.join(map(str, range(l, l + 4)) if l % 2 == 0 else map(str, range(l + 1, l + 5)))]
    elif l == 1: res = ['0', '3', ' '.join(map(str, range(1, 4)))]
    elif l == 3: res = ['0', '3', ' '.join(map(str, [3, 5, 6]))]
    else: res = ['1', '2', ' '.join([str(l + 1), str(l + 2)])]
    print '\n'.join(res)
else:
    res = ['0', '4', ' '.join(map(str, range(l, l + 4)) if l % 2 == 0 else map(str, range(l + 1, l + 5)))]
    print '\n'.join(res)