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:
#!/usr/bin/python3

import sys
import itertools
import functools

def brute_force(l, r, k):
    best_set = None
    best = None

    for i in range(1, k+1):
        for s in itertools.combinations(range(l, r+1), i):
            p = functools.reduce(lambda x, y: x^y, s)
            if (best is None) or p < best:
                best = p
                best_set = s

    print(best)
    print(len(best_set))
    print(' '.join(str(x) for x in best_set))


if __name__ == '__main__':

    l, r, k = map(int, sys.stdin.readline().split())
    n = r - l + 1
    if k > 4:
        k = 4
    # 1 <= k <= 4

    if n < 7:
        brute_force(l, r, k)
        sys.exit(0)

    if k == 1:
        print(l)
        print(1)
        print(l)
        sys.exit(0)

    if k == 3:
        w = len(bin(r)) - 2
        # print(w)
        for i in range(0, w-2+1):
            a = int('1' + '0' * i + '1' + '0' * (w-2-i), 2)
            b = int('1' + '0' * i + '0' + '1' * (w-2-i), 2)
            c = int('0' + '0' * i + '1' + '1' * (w-2-i), 2)
            # print('*', c, b, a)
            if l <= c and a <= r:
                print(0)
                print(3)
                print(c, b, a)
                sys.exit(0)

    if 2 <= k <= 3:
        while l % 4 != 0:
            l += 1
        print(1)
        print(2)
        print(l, l+1)
        sys.exit(0)

    # k == 4
    while l % 4 != 0:
            l += 1
    print(0)
    print(4)
    print(l, l+1, l+2, l+3)