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.*;
import java.util.*;
import java.util.List;

public class Main {
    private static StringTokenizer st;
    private static BufferedReader br;

    public static void print(Object x) {
        System.out.println(x + "");
    }
    public static String join(List<?> x, String space) {
        StringBuilder sb = new StringBuilder();
        for (Object elt : x) {
            sb.append(elt);
            sb.append(space);
        }
        return sb.toString();
    }

    public static String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine().trim());
        }
        return st.nextToken();
    }
    public static double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public static int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public static List<Double> nextDoubles(int n) throws IOException{
        List<Double> lst = new ArrayList<Double>();
        for (int i = 0; i < n; i++) {
            lst.add(nextDouble());
        }
        return lst;
    }
    public static List<Integer> nextInts(int n) throws IOException{
        List<Integer> lst = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            lst.add(nextInt());
        }
        return lst;
    }
    public static List<Integer> emptyList(int n, int val) {
        List<Integer> lst = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            lst.add(val);
        }
        return lst;
    }

    public static class Fenwick {
        List<Integer> treeValues;
        int length;

        public Fenwick(int length) {
            this.length = length;
            treeValues = new ArrayList<Integer>();
            for (int i = 0; i <= length; i++) {
                treeValues.add(0);
            }
        }

        public int get(int i) {
            return getCumulative(i) - getCumulative(i - 1);
        }

        public int getCumulative(int i) {
            //print("Getting cumulative " + i);
            int total = 0;
            while (i > 0) {
                total += treeValues.get(i);
                i -= (i & -i);
            }
            return total;
        }

        public void increment(int i, int val) {
            //print("Incrementing " + i);
            while (i <= length) {
                treeValues.set(i, treeValues.get(i) + val);
                i += (i & -i);
            }
        }

        public void set(int i, int val) {
            increment(i, val - get(i));
        }
    }

    public static List<List<Long>> subsets(long l, long r, int k) {
        List<List<Long>> all = new ArrayList<List<Long>>();
        for (List<Long> subset : subsets(l, r)) {
            if (subset.size() <= k) {
                all.add(subset);
            }
        }
        return all;
    }

    public static List<List<Long>> subsets(long l, long r) {
        if (l > r) {
            return Arrays.asList((List<Long>) new ArrayList<Long>());
        }
        List<List<Long>> all = new ArrayList<List<Long>>();
        for (List<Long> subset : subsets(l + 1, r)) {
            all.add(subset);
            subset = new ArrayList<Long>(subset);
            subset.add(l);
            all.add(subset);
        }
        return all;
    }

    public static long xor(List<Long> set) {
        long result = 0;
        for (long val : set) {
            result = result ^ val;
        }
        return result;
    }

    public static long highestBit(long x) {
        long pow = (long) (Math.log(x) / Math.log(2));
        return (long) Math.pow(2, pow);
    }

    public static List<Long> bruteForce(long l, long r, int k) {
        List<Long> best = Arrays.asList(l);
        for (List<Long> subset : subsets(l, r, k)) {
            if (subset.size() == 0) continue;
            if (xor(subset) < xor(best)) {
                best = subset;
            }
        }
        return best;
    }

    public static String solve(long l, long r, int k) {
        List<Long> best;
        if (r - l <= 10) {
            best = bruteForce(l, r, k);
        } else {
            if (k == 1) {
                best = Arrays.asList(l);
            } else if (k == 2) {
                long start = 2*(l/2) + 2;
                best = Arrays.asList(start, start + 1);
            } else if (k == 3) {
                long p = highestBit(l);
                if (r >= 3 * p) {
                    best = Arrays.asList(l, 3 * p, l + p);
                } else {
                    long start = 2*(l/2) + 2;
                    best = Arrays.asList(start, start + 1);
                }
            } else {
                long start = 2*(l/2) + 2;
                best = Arrays.asList(start, start + 1, start + 2, start + 3);
            }
        }

        print(xor(best));
        print(best.size());
        print(join(best, " "));
        return "";
    }

    public static void main(String[] args) throws Exception {
        boolean debug = false;
        InputStream in = System.in;
        if (debug) {
            in = new FileInputStream("input.in");
        }
        br = new BufferedReader(new InputStreamReader(in));

        long l = nextLong();
        long r = nextLong();
        int k = nextInt();
        print(solve(l, r, k));
    }
}