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 PYTHON3):

Solution:
def main():
    from itertools import combinations
    from functools import reduce
    from random import randrange
    
    l, r, k = [int(i) for i in input().split()]
    
    if r - l < 4:
        f = float("inf")
        result = None
        numbers = list(range(l, r + 1))
        for mask in range(1, 1 << (r - l + 1)):
            tmp = [numbers[i] for i in range(r - l + 1) if mask & (1 << i)]
            if len(tmp) <= k and reduce(lambda x, y: x ^ y, tmp) < f:
                f = reduce(lambda x, y: x ^ y, tmp)
                result = tmp
    elif k >= 4:
        a = l + l % 2
        f = 0
        result = [a, a + 1, a + 2, a + 3]
    elif k == 1:
        f = l
        result = [l]
    elif k == 2:
        a = l + l % 2
        f = 1
        result = [a, a + 1]
    elif k == 3:
        a = l + l % 2
        f = 1
        result = [a, a + 1]
        for a in range(l, min(r + 1, l + 400)):
            for b in range(max(l, r - 400), r + 1):
                if l <= a ^ b <= r:
                    f = 0
                    result = [a, b, a ^ b]
                    break
        for i in range(100000):
            a = randrange(l, r + 1)
            b = randrange(l, r + 1)
            if l <= a ^ b <= r:
                f = 0
                result = [a, b, a ^ b]
                break
        
        
    print(f)
    print(len(result))
    print(' '.join(str(i) for i in sorted(result)))


main()