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 implements Runnable {
		
	public void solve() throws IOException {
		long l = nextLong(), r = nextLong();
                long k = nextLong();
                if(r - l + 1 <= 12){
                    int len = (int)(r - l + 1);
                    long bestXor = l;
                    int bestMask = 1;
                    for(int i = 1;i < (1 << len); i++){
                        if(Integer.bitCount(i) <= k){
                            long curXor = 0;
                            
                            for(int m = 0; m < len; m++){
                                if((i & (1 << m)) > 0){
                                    curXor = curXor ^ (l+m);
                                }
                            }
                            
                            if(curXor < bestXor){
                                bestXor = curXor;
                                bestMask = i;
                            }
                        }
                    }
                    
                    System.out.println(bestXor);
                    System.out.println(Integer.bitCount(bestMask));
                    for(int i = 0; i < len; i++){
                        if((bestMask & (1 << i)) != 0)
                            System.out.print((l+i) + " ");
                    }
                    System.out.println();
                }
                else{
                    if(k == 1){
                        System.out.println(l);
                        System.out.println("1");
                        System.out.println(l);
                    }
                    else if(k == 2){
                        long from = (l/2) * 2 + 2;
                        System.out.println(1);
                        System.out.println(2);
                        System.out.println(from + " " + (from+1));
                    }
                    else if(k == 3){
                        long first = 1, second = 2, third = 3;
                        while(third <= r){
                            if(first >= l){
                                System.out.println(0);
                                System.out.println(3);
                                System.out.println(first + " " + second + " " + third);
                            return;
                            }
                            
                            first = first * 2 + 1;
                            second = second * 2 + 1;
                            third = third * 2;
                        }
                        
                        long from = (l/2) * 2 + 2;
                        System.out.println(1);
                        System.out.println(2);
                        System.out.println(from + " " + (from+1));
                    }
                    else{
                        long from = (l/4) * 4 + 4;
                        System.out.println(0);
                        System.out.println(4);
                        for(int i = 0; i < 4; i++){
                            System.out.print((from + i) + " ");
                        }
                        System.out.println();
                    }
                }
	}

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

        public void print1Int(int[] a){
                for(int i = 0; i < a.length; i++)
                        System.out.print(a[i] + " ");
                System.out.println();
        }
        
        public void print2Int(int[][] a){
                for(int i = 0; i < a.length; i++){
                        for(int j = 0; j < a[0].length; j++){
                                System.out.print(a[i][j] + " ");
                        }
                        System.out.println();
                }
        }
        
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tok = null;
			solve();
			in.close();
		} catch (IOException e) {
			System.exit(0);
		}
	}

	public String nextToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	BufferedReader in;
	StringTokenizer tok;
}