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:
from itertools import combinations
from functools import reduce
def get_res(l, r, k):
    if k == 1:
        return [l]
    if r == l:
        return [l]
    if r - l == 1:
        if r ^ l < l:
            return [r, l]
        else:
            return [l]
    if k == 2:
        return [l + (l % 2), l + 1 + (l % 2)]
    moi = 2 ** (len(bin(l)) - 2)
    if moi + moi // 2 <= r:
        return [l, moi + moi // 2, l ^ (moi + moi // 2)]
    if k == 3:
        return [l + (l % 2), l + 1 + (l % 2)]
    next4 = l + (4 - (l % 4)) % 4
    if next4 + 3 <= r:
        return [next4, next4 + 1, next4 + 2, next4 + 3]
    tempres = l
    tempans = [l]
    for ll in range(2, k + 1):
        for s in combinations(range(l, r + 1), ll):
            rs = reduce(lambda x, y: x ^ y, s, 0)
            if rs < tempres:
                tempans = s
                tempres = rs
    return tempans
l, r, k = map(int, input().split())
res = get_res(l, r, k)
s = 0
for i in res:
    s ^= i
print(s)
print(len(res))
print(*res)