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:
import math

splitted = raw_input().split(' ')
l = int(splitted[0])
r = int(splitted[1])
k = int(splitted[2])

if k == 1:
    print l
    print 1
    print l
elif k == 2:
    if l + 1 < r and l & 1 == 1:
        l += 1
    if l < (l ^ (l + 1)):
        print l, '\n1\n', l
    else:
        print (l ^ (l + 1)), '\n2\n', l, (l + 1)
elif k == 3:    
    for i in xrange(0, 41):
        if (3 << i) < l:
            continue
        if (3 << i) > r:
            break
        if (1 << i) + (2 ** i - 1) >= l:
            print "0\n3\n", (3 << i), (2 << i) + (2 ** i - 1), (1 << i) + (2 ** i - 1)
            exit(0)
    if (l & 1) == 1:
        l += 1
    print "1\n2\n", l, (l + 1)        
else:
    num = r - l + 1
    if num >= 7:
        while (l & 3) > 0:
            l += 1
        print 0
        print 4
        print l, (l + 1), (l + 2), (l + 3)
    else:
        answ = [l]
        mn = l
        mx = 2 ** num
        for i in xrange(2, mx):
            xor = 0
            rt = 0
            for j in xrange(0, num + 1):
                if (i & (1 << j)) > 0:
                    rt += 1
                    xor = (xor ^ (l + j))
            if rt <= k and xor < mn:                
                mn = xor
                answ = []
                for j in xrange(0, num):
                    if (i & (1 << j)) > 0:
                        answ.append(l + j)
        print mn
        print len(answ)
        for g in answ:
            print g,