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:
def main():
    l, r, k = map(int, raw_input().split())
    def bf():
        ans = r
        ansl = [r]
        for i in xrange(1, 1 << (r - l + 1)):
            x, a = 0, []
            for j in xrange(r - l + 1):
                if i >> j & 1:
                    x = x ^ (l + j)
                    a.append(l + j)
            if x < ans:
                ans = x
                ansl = a
        print ans
        print len(ansl)
        for x in ansl:
            print x,
    def go2(b, a, t):
        la = len(bin(a)) - 2
        lb = len(bin(b)) - 2
        if lb < la:
            return [-1]
        if b > a:
            return [a, t, t + a]
        k = (1 << la) - 1
        return [k, t + b, t + (b ^ k)]
    def go(a, b):
        la = len(bin(a)) - 2
        lb = len(bin(b)) - 2
        if la == lb:
            return [-1]
        t = 1 << (lb - 1)
        res = go2(b - t, a, t)
        if res[0] != -1:
            return res
        else:
            return go(a, t-1)
    if k == 1:
        print l
        print 1
        print l
        return
    elif k >= 4:
        if r - l >= 4:
            print 0
            print 4
            if l % 2 == 1:
                print l + 1, l + 2, l + 3, l + 4
            else:
                print l, l + 1, l + 2, l + 3
        else:
            bf()
        return
    elif k == 3:
        res = go(l, r)
        if res[0] != -1:
            print 0
            print 3
            for x in res:
                print x,
            return
    if r - l == 1:
        bf()
    else:
        print 1
        print 2
        if l % 2 == 1:
            print l + 1, l + 2
        else:
            print l, l + 1
main()