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.IOException;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.NoSuchElementException;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Stanislav Pak
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
		long l = in.readLong();
		long r = in.readLong();
		int k = in.readInt();
		Random random = new Random();
		if (r - l + 1 <= 10) {
			brute(l, r, k, out);
		} else {
			if (k == 1) {
				out.printLine(l);
				out.printLine(1);
				out.printLine(l);
			} else if (k  == 2) {
				while (l % 4 > 0) ++l;
				out.printLine(1);
				out.printLine(2);
				out.printLine(l + " " + (l + 1));
			} else if (k == 3) {
				long a = 3;
				long b = 2;
				long c = 1;
				while (c < l) {
					c <<= 1;
					++c;
					b <<= 1;
					++b;
					a <<= 1;
				}
				if (a <= r) {
					out.printLine(0);
					out.printLine(3);
					out.printLine(a + " " + b + " " + c);
					return;
				}
				while (l % 4 > 0) ++l;
				out.printLine(1);
				out.printLine(2);
				out.printLine(l + " " + (l + 1));
			} else {
				while (l % 4 > 0) ++l;
				out.printLine(0);
				out.printLine(4);
				out.printLine(l + " " + (l + 1) + " " + (l + 2) + " "  + (l + 3));
			}
		}
    }

	private void brute(long l, long r, int k, OutputWriter out) {
		int n = (int) (r - l + 1);
		long ans = -1;
		int bmask = -1;
		for (int mask = 1; mask < (1 << n); ++mask) {
			if (Integer.bitCount(mask) <= k) {
				long x = 0;
				for (int i = 0; i < n; ++i) {
					if ((mask & (1 << i)) > 0) {
						x ^= l + i;
					}
				}
				if (ans == -1 || ans > x) {
					ans = x;
					bmask = mask;
				}
			}
		}
		out.printLine(ans);
		out.printLine(Integer.bitCount(bmask));
		boolean first = true;
		for (int i = 0; i < n; ++i) {
			if ((bmask & (1 << i)) > 0) {
				if (!first) out.print(" ");
				first = false;
				out.print(l + i);
			}
		}
		out.printLine();
	}
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	public static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine() {
		writer.println();
	}

    public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	public void print(long i) {
		writer.print(i);
	}

	public void printLine(long i) {
		writer.println(i);
	}

	public void printLine(int i) {
		writer.println(i);
	}
}