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 static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

/**
 * @author master_j
 * @version 0.4
 * @since May 3, 2014
 */
public class Main {
    private void solve() throws IOException {
        long l = io.nL(), r = io.nL(), k = io.nI();
        io.wln(solve(l, r, k));
    }//2.2250738585072012e-308

    private String solve(long l, long r, long k) throws IOException {
        if(k == 1 || l == r)
            return String.format("%d\n1\n%d\n", l, l);

        if(k == 2 || l + 1 == r){
            long ans = l;
            for(long t = l; t + 1 <= r && t <= l + 1000; t++)
                if((ans ^ (1 + ans)) > (t ^ (1 + t)))
                    ans = t;
            if((ans ^ (1 + ans)) < l)
                return String.format("%d\n2\n%d %d\n", ans ^ (1 + ans), ans, 1 + ans);
            else
                return String.format("%d\n1\n%d\n", l, l);
        }

        if(l == 1 && 3 <= r)
            return "0\n3\n1 2 3\n";

        String ans2 = "";
        long f2 = Long.MAX_VALUE;
        for(long p = l; p <= l + 40; p++)
            for(long q = p + 1; q <= p + 40; q++){
                if(r < p || r < q)
                    continue;
                long t = p ^ q;
                if(f2 > t){
                    f2 = t;
                    ans2 = String.format("%d\n2\n%d %d\n", f2, p, q);
                }
            }

        long f3 = Long.MAX_VALUE;
        String ans3 = "";
        for (long p = l; p <= l + 40; p++)
            for (long q = p + 1; q <= p + 40; q++)
                for (long w = q + 1; w <= q + 40; w++) {
                    if (r < p || r < q || r < w)
                        continue;
                    long t = p ^ q ^ w;
                    if (f3 > t) {
                        f3 = t;
                        ans3 = String.format("%d\n3\n%d %d %d\n", f3, p, q, w);
                    }
                }

        long f4 = Long.MAX_VALUE;
        String ans4 = "";
        if(k >= 4){
            final int Y = 25;
            for (long p = l; p <= l + Y; p++)
                for (long q = p + 1; q <= p + Y; q++)
                    for (long w = q + 1; w <= q + Y; w++)
                        for (long s = w + 1; s <= w + Y; s++){
                            if (r < p || r < q || r < w || r < s)
                                continue;
                            long t = p ^ q ^ w ^ s;
                            if (f4 > t) {
                                f4 = t;
                                ans4 = String.format("%d\n4\n%d %d %d %d\n", f4, p, q, w, s);
                            }
                        }
        }

        if(k >= 3){
            int t = (int)(log(l)/log(2)) + 1;
            long p2 = 1;
            for(int i = 0; i < t; i++)
                p2 *= 2;

            long q = p2 + p2 / 2;
            long p = q ^ l;

            if(p <= r && q <= r){
                f3 = 0;
                ans3 = String.format("0\n3\n%d %d %d\n", l, p, q);
            }
        }

        if(f2 <= f3 && f2 <= f4)
            return ans2;

        if(f3 <= f2 && f3 <= f4)
            return ans3;

        if(f4 <= 12 && f4 <= f2 && f4 <= f3)
            return ans4;

        throw new IOException();
    }

    public static void main(String[] args) throws IOException {
        IO.launchSolution(args);
    }

    Main(IO io) throws IOException {
        this.io = io;
        solve();
    }

    private final IO io;
}

class IO {
    static final String _localArg = "master_j";
    private static final String _problemName = "";
    private static final IO.Mode _inMode = Mode.STD_;
    private static final IO.Mode _outMode = Mode.STD_;
    private static final boolean _autoFlush = false;

    static enum Mode {STD_, _PUT_TXT, PROBNAME_}

    private final StreamTokenizer st;
    private final BufferedReader br;
    private final Reader reader;

    private final PrintWriter pw;
    private final Writer writer;

    static void launchSolution(String[] args) throws IOException {
        boolean local = (args.length == 1 && args[0].equals(IO._localArg));
        IO io = new IO(local);

        long nanoTime = 0;
        if (local) {
            nanoTime -= System.nanoTime();
            io.wln("<output>");
        }

        io.flush();
        new Main(io);
        io.flush();

        if(local){
            io.wln("</output>");
            nanoTime += System.nanoTime();
            final long D9 = 1000000000, D6 = 1000000, D3 = 1000;
            if(nanoTime >= D9)
                io.wf("%d.%d seconds\n", nanoTime/D9, nanoTime%D9);
            else if(nanoTime >= D6)
                io.wf("%d.%d millis\n", nanoTime/D6, nanoTime%D6);
            else if(nanoTime >= D3)
                io.wf("%d.%d micros\n", nanoTime/D3, nanoTime%D3);
            else
                io.wf("%d nanos\n", nanoTime);
        }

        io.close();
    }

    IO(boolean local) throws IOException {
        if(_inMode == Mode.PROBNAME_ || _outMode == Mode.PROBNAME_)
            if(_problemName.length() == 0)
                throw new IllegalStateException("You imbecile. Where's my <_problemName>?");

        if(_problemName.length() > 0)
            if(_inMode != Mode.PROBNAME_ && _outMode != Mode.PROBNAME_)
                throw new IllegalStateException("You imbecile. What's the <_problemName> for?");

        Locale.setDefault(Locale.US);

        if (local) {
            reader = new FileReader("input.txt");
            writer = new OutputStreamWriter(System.out);
        } else {
            switch (_inMode) {
                case STD_:
                    reader = new InputStreamReader(System.in);
                    break;
                case PROBNAME_:
                    reader = new FileReader(_problemName + ".in");
                    break;
                case _PUT_TXT:
                    reader = new FileReader("input.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _inMode.");
            }
            switch (_outMode) {
                case STD_:
                    writer = new OutputStreamWriter(System.out);
                    break;
                case PROBNAME_:
                    writer = new FileWriter(_problemName + ".out");
                    break;
                case _PUT_TXT:
                    writer = new FileWriter("output.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _outMode.");
            }
        }

        br = new BufferedReader(reader);
        st = new StreamTokenizer(br);

        pw = new PrintWriter(writer, _autoFlush);

        if(local && _autoFlush)
            wln("Note: auto-flush is on.");
    }

    void wln()          {pw.println(); }
    void wln(boolean x) {pw.println(x);}
    void wln(char x)    {pw.println(x);}
    void wln(char x[])  {pw.println(x);}
    void wln(double x)  {pw.println(x);}
    void wln(float x)   {pw.println(x);}
    void wln(int x)     {pw.println(x);}
    void wln(long x)    {pw.println(x);}
    void wln(Object x)  {pw.println(x);}
    void wln(String x)  {pw.println(x);}

    void wf(String f, Object...o){pw.printf(f, o);}

    void w(boolean x)   {pw.print(x);}
    void w(char x)      {pw.print(x);}
    void w(char x[])    {pw.print(x);}
    void w(double x)    {pw.print(x);}
    void w(float x)     {pw.print(x);}
    void w(int x)       {pw.print(x);}
    void w(long x)      {pw.print(x);}
    void w(Object x)    {pw.print(x);}
    void w(String x)    {pw.print(x);}

    int nI() throws IOException    {st.nextToken(); return (int)st.nval;}
    double nD() throws IOException {st.nextToken(); return st.nval;}
    float nF() throws IOException  {st.nextToken(); return (float)st.nval;}
    long nL() throws IOException   {st.nextToken(); return (long)st.nval;}
    String nS() throws IOException {st.nextToken(); return st.sval;}

    void wc(String x){ wc(x.toCharArray()); }
    void wc(char c1, char c2){for(char c = c1; c<=c2; c++)wc(c);}
    void wc(char x[]){
        for(char c : x)
            wc(c);
    }
    void wc(char x){st.ordinaryChar(x); st.wordChars(x, x);}

    public boolean eof() {return st.ttype == StreamTokenizer.TT_EOF;}
    public boolean eol() {return st.ttype == StreamTokenizer.TT_EOL;}

    void flush(){pw.flush();}
    void close() throws IOException{reader.close(); br.close(); flush(); pw.close();}
}