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.*;

public class D
{

	FastScanner in;
	PrintWriter out;
	int i = 0, j = 0;


	void solve() {
		/**************START**************/
		long l = in.nextLong(), r = in.nextLong(), k = in.nextLong();
		if (k == 1 || l == r)
		{
			out.println(l);
			out.println("1");
			out.println(l);
		}
		else if (k == 2 || (r-l < 2))
		{
			if (r-l == 1)
			{
				if ((l ^ r) < l)
				{
					out.println((l^r));
					out.println("2");
					out.println(l + " " + r);
				}
				else
				{
					out.println(l);
					out.println("1");
					out.println(l);
				}
			}
			else
			{
				if (l % 2 == 1)
					l++;
				out.println("1");
				out.println("2");
				out.println(l + " " + (l+1));
			}
		}
		else if (k == 3)
		{
			if (l == 1)
			{
				out.println("0");
				out.println("3");
				out.println("1 2 3");
				return;
			}
			long highBit = Long.highestOneBit(l);
			long lowerBound = highBit * 2;
			long upperBound = lowerBound + highBit;
			lowerBound--;
			if (upperBound <= r)
			{
				long midBound = (upperBound ^ lowerBound);
				out.println("0");
				out.println("3");
				out.println(lowerBound + " " + midBound + " " + upperBound);
			}
			else
			{
				if (l % 2 == 1)
					l++;
				out.println("1");
				out.println("2");
				out.println(l + " " + (l+1));
			}
		}
		else
		{
			if (l == 1)
			{
				out.println("0");
				out.println("3");
				out.println("1 2 3");
				return;
			}
			else if (l == 3)
			{
				out.println("0");
				out.println("3");
				out.println("3 5 6");
				return;
			}

			if (l % 2 == 1)
			{
				l++;
			}
			if (r - l >= 3)
			{
				out.println("0");
				out.println("4");
				out.println(l + " " + (l+1) + " " + (l+2) + " " + (l+3));
			}
			else
			{
				out.println("1");
				out.println("2");
				out.println(l + " " + (l+1));
			}
			

		}











		/***************END***************/
	}

	public static void main(String[] args) {
		new D().runIO();
	}

	void runIO() {
		in = new FastScanner(System.in);
		out = new PrintWriter(System.out);

		solve();

		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		//This will empty out the current line (if non-empty) and return the next line down. If the next line is empty, will return the empty string.
		String nextLine() {
				st = null;
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				return s;
		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}