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

public class Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	return Integer.parseInt(next());
    }
    
    private long nextLong() throws Exception{
	return Long.parseLong(next());
    }
    
    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);
	long l = nextLong(), r = nextLong();
	int k = nextInt();
	
	if (k == 1){
	    out.println(l);
	    out.println(1);
	    out.println(l);
	    out.close();
	    return;
	}
	
	if (r - l <= 4){
	    long []a = new long[(int)(r-l+1)];
	    for(long i=l;i<=r;i++){
		a[(int)(i-l)] = i;
	    }
	    
	    long min = Long.MAX_VALUE;
	    int msk = 0;
	    
	    int n = (int)(r - l + 1);
	    for(int mask=1;mask<(1<<n);mask++){
		if (Integer.bitCount(mask) <= k){
		    long xor = 0;
		    for(int i=0;i<n;i++){
			if ((mask & (1 << i)) > 0) xor^=a[i];
		    }
		    if (xor < min){
			min = xor;
			msk = mask;
		    }
		}
	    }
	    out.println(min);
	    out.println(Integer.bitCount(msk));
	    for(int i=0;i<n;i++){
		if ((msk & (1 << i)) > 0){
		    out.print(a[i] + " ");
		}
	    }
	    out.println();
	    out.close();
	    return;
	}else{
	    if (k == 2){
		if (l % 2 == 1) l++;
		out.println(1);
		out.println(2);
		out.println(l + " " + (l+1));
		out.close();
		return;
	    }
	    if (k >= 4){
		if (l % 2 == 1) l++;
		out.println(0);
		out.println(4);
		out.print(l + " " + (l+1) + " ");
		out.print((l+2) + " " + (l+3));
		out.println();
		out.close();
		return;
	    }
	    
	    long block = 3;
	    int i = 0;
	    while((block << i) <= r){
		long x = block << i;
		long y = ((1L<<(i+2))-1) ^ (1L<<i);
		long z = ((1L<<(i+2))-1) ^ (1L<<(i+1));
		
		//System.out.println(Long.toString(x, 2));
		//System.out.println(Long.toString(y, 2));
		//System.out.println(Long.toString(z, 2));
		//System.out.println();
		if (z >= l){
		    out.println(0);
		    out.println(3);
		    out.println(x + " " + y + " " + z);
		    out.close();
		    return;
		}
		i++;
	    }
	    if (l % 2 == 1) l++;
	    
	    out.println(1);
	    out.println(2);
	    out.println(l + " " + (l+1));
	}
	
        out.close();
    }

    public static void main(String args[]) throws Exception{
	new Main().run();
    }
}