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 static java.lang.Math.*; 

import java.io.*; 
import java.util.*; 
import java.math.*;

public class A {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 

	String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}

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

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

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

	int inf = 1100000000; 


	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		//Long start = System.currentTimeMillis();

		long l = nextLong();
		long r = nextLong();
		long k = nextLong();

		if (k == 1) {
			out.println(l);
			out.println(1); 
			out.println(l); 
			out.close(); 
			System.exit(0);
		}
			long ans=l;
			long sz=1, start=l;
			for (long i=l; i<=min(r, l + 10000); i++) {
				for (long q=1; q<=min(4, k); q++) {
					long res=0;
					if (i + q - 1 > r) break;
					for (long j=i; j<i+q; j++) res^=j;
					//if (q == 3) System.err.println(res);
					if (ans > res) {
						ans = res;
						sz = q;
						start = i; 
					}
				}
			}

			if (k >= 3 && ans > 0) {
					long x = 1, y = 2, z = 3;
		for (int i = 0; i < 55; i++) {
			if (x >= l && z <= r) {
				
				out.println(0);
				out.println(3); 
				out.println(x + " " + y + " " + z);
				out.close();
				System.exit(0); 
			}
			x = (x << 1) + 1;
			y = (y << 1) + 1;
			z = z << 1;
		}
			}

			out.println(ans); 
			out.println(sz); 
			for (long i=0; i<sz; i++) out.print((start + i)+" ");
		
		out.close(); 
 	}
	
	public static void main(String[] args) throws Exception {
		new A().run(); 
	}

}