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

public class CF262D {
//	public static long iter (Set<Long> nums, long size) {
//		if (size == 0) 
//			return 0;
//		else {
//			long min = Long.MAX_VALUE;
//			
//			for (long x : nums) {
//				nums.remove(x);
//				min = Math.min(min, 
//						iter(nums, size - 1) ^ x);
//				nums.add(x);
//			}
//			
//			return min;
//		}
//	}
	
	// finds a subset S of [l, r] with size at most k such that 
	// f(S) is minimal amongst all possible subsets
	public static Set<Long> findMinSet (long left, long r, long k) {
		long min = Long.MAX_VALUE;
		Set<Long> minSet = new HashSet<Long>();
		long motherSize = r - left + 1; 
		
		Set<Long> candidateSet = new HashSet<Long>();
	
		// m indicates set membership
		for (long m = 1; m < (1 << motherSize); m++) {
			if (Long.bitCount(m) <= k) {
				candidateSet.clear();
				
				long xorVal = 0L;
				
				for(long i = left; i <= r; i++) {
					// if i is selected by m
					if ((1 & (m >> (r - i))) == 1) {
						xorVal ^= i;
						candidateSet.add(i);
					}
				}
				
				if (xorVal < min) {
					min = xorVal;
					minSet.clear();
					minSet.addAll(candidateSet);						
				} else {
					candidateSet.clear();
				}
			}
		}
	
		return minSet;
	}
	
	
	public static void main (String [] args) {

		Scanner input = new Scanner(System.in);
		
		long left = input.nextLong();
		long r = input.nextLong();
		long k = input.nextLong();
		
		if (k == 1) {
			System.out.println(left);
			System.out.println(1);
			System.out.println(left);
		} else {
			if (r - left <= 4) {
				// brute-force
				Set<Long> minSet = findMinSet(left, r, k);
				
				long xor = 0;
				for (long num : minSet) {
					xor ^= num;
				}
				
				System.out.println(xor);
				System.out.println(minSet.size());
				
				for (long num : minSet) {
					System.out.print(num + " ");
				}
				System.out.println();
			} else {
				if (k == 2) {			
					System.out.println(1);
					System.out.println(2);
					
					if (left % 2 == 0)
						System.out.println(left + " " + (left+1));
					else
						System.out.println((left+1) + " " + (left+2));
					
				} else if (k == 3) {
					// check if f(S) = 0 is feasible
					boolean zeroFeasible = false;
					
					for (int e = 1; e < 45; e++) { // 2^44 is far larger than 10^9
						long z = ((long) 1 << e) - 1;
						
						if (z > r)
							break;
						
						if (z >= left && z <= r) {
							long y = ((long) 1 << e) + (((long) 1 << (e - 1)) - 1);
							long x = ((long) 1 << e) + ((long) 1 << (e - 1));
							if (x > r)
								break;							
							
							if ((x ^ y ^ z) == 0) {
								System.out.println(0);
								System.out.println(3);
								System.out.println(x + " " + y + " " + z);
								zeroFeasible = true;
								break;
							}
						}
					}
					if (!zeroFeasible) {
						System.out.println(1);
						System.out.println(2);
						
						if (left % 2 == 0)
							System.out.println(left + " " + (left+1));
						else
							System.out.println((left+1) + " " + (left+2));
					}
				} else { // k >= 4 
					System.out.println(0);
					System.out.println(4);
					if (left % 2 == 0)
						System.out.println(left + " " + (left+1) + " " + (left+2) + " " + (left+3) );
					else
						System.out.println((left+1) + " " + (left+2) + " " + (left+3) + " " + (left+4));
					
				}
			}
		}
		
		input.close();
	}
}