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

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class LittleVictorSet {
    
    static final long INF = (long) 1e18;
    
    long l, r;
    int k;
    
    void solve() {
        l = in.nextLong();
        r = in.nextLong();
        k = in.nextInt();
        
        if (r - l + 1 < 5) go1();
        else go2();
    }
    
    void go1() {
        long n = r - l + 1;
        long ans = INF;
        List<Long> res = new ArrayList<>();
        for (int i = 1; i < 1 << n; i++) {
            if (Long.bitCount(i) > k) continue;
            long xor = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) xor ^= l + j;
            }
            if (xor < ans) {
                ans = xor;
                res.clear();
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) > 0) res.add(l + j);
                }
            }
        }
        
        out.println(ans);
        out.println(res.size());
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) out.print(' ');
            out.print(res.get(i));
        }
        out.println();
    }
    
    void go2() {
        if (k == 1) {
            out.println(l);
            out.println(1);
            out.println(l);
            return;
        }
        
        if (k == 2) {
            out.println(1);
            out.println(2);
            if (l % 2 == 0) out.printf("%d %d%n", l, l + 1);
            else out.printf("%d %d%n", l + 1, l + 2);
            return;
        }
        
        if (k >= 4) {
            out.println(0);
            out.println(4);
            if (l % 2 == 0) out.printf("%d %d %d %d%n", l, l + 1, l + 2, l + 3);
            else out.printf("%d %d %d %d%n", l + 1, l + 2, l + 3, l + 4);
            return;
        }
        
        long min = 1, max = 3;
        while (max <= r) {
            if (min >= l) {
                out.println(0);
                out.println(3);
                out.printf("%d %d %d%n", min, max - 1, max);
                return;
            }
            min <<= 1;
            min++;
            max <<= 1;
        }
        out.println(1);
        out.println(2);
        if (l % 2 == 0) out.printf("%d %d%n", l, l + 1);
        else out.printf("%d %d%n", l + 1, l + 2);
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new LittleVictorSet().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}