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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Round262_D {
	
	
	public boolean check(long l, long r, long a, long b, long c){
		return (a >= l && a <= r && b >= l && b <= r && c >= l && c <= r && a != b && b != c && a != c);
	}

	public ArrayList<Long> suggestThree(long l, long r, int type){
		
		if(type == 0){
			String rBin = Long.toBinaryString(r);
			if(rBin.charAt(1) == '0')
				return null;
			StringBuffer other = new StringBuffer();
			other.append('1');
			for(int i = 1;i < rBin.length();i++)
				other.append((rBin.charAt(i) == '0')?'1':'0');
			long val = Long.parseLong(other.toString(), 2);
			
			if(check(l,r, val, r, val^r))
			{
				ArrayList<Long> arr = new ArrayList<Long>();
				arr.add(val);arr.add(r);arr.add(val^r);
				return arr;
			}
			return null;
		}else{
			
			int bits = Long.toBinaryString(r).length()-1;
			long a = (1L<<bits)-1; 
			long b = (1L<<(bits-1));
			long c = a^b;
			
			if(check(l,r, a, b, c))
			{
				ArrayList<Long> arr = new ArrayList<Long>();
				arr.add(a);arr.add(b);arr.add(c);
				return arr;
			}
			return null;
		}
	}
	
	
	public ArrayList<Long> canZeroThree(long l, long r, long k){
		if(r-l+1 < 3 || k < 3)
			return null;
		ArrayList<Long> arr1 = suggestThree(l,r,0);
		ArrayList<Long> arr2 = suggestThree(l,r,1);
		if(arr1 == null)return arr2;
		else if(arr2 == null)return arr1;
		else return (getXor(arr1)< getXor(arr2))?arr1:arr2;
	}
	
	public ArrayList<Long> canZeroFour(long l, long r, long k) {
	if(k < 4)
		return null;
	if (l % 2 == 1)
		l++;
	if (r - l >= 3) {
		ArrayList<Long> arr = new ArrayList<Long>();
		for (int i = 0; i < 4; i++) {
			arr.add(l + i);
		}
		return arr;
	}
	return null;
	}

	
	public long getXor(ArrayList<Long> arr){
		long x=0;
		for(long z:arr)
			x ^= z;
		return x;
	}
	public ArrayList<Long> canZero(long l, long r, long k) {
		ArrayList<Long> arr1 = canZeroThree(l, r, k);
		ArrayList<Long> arr2 = canZeroFour(l, r, k);
		if(arr1 == null)
			return arr2;
		else if(arr2 == null)
			return arr1;
		else 
			return (getXor(arr1) < getXor(arr2))?arr1:arr2;
	}

	public void solve() throws Exception {
		InputReader in = new InputReader();
		long l = in.nextLong();
		long r = in.nextLong();
		long k = in.nextLong();
		String a, b, c;

		ArrayList<Long> listZero;
		if (k == 1 || l == r) {
			a = l + "";
			b = 1 + "";
			c = l + "";
		} else if (r - l == 1) {
			if ((l ^ r) < l) {
				a = (l ^ r) + "";
				b = 2 + "";
				c = l + " " + r;
			} else {
				a = l + "";
				b = 1 + "";
				c = l + "";
			}
		} else if ((listZero = canZero(l, r, k)) != null) {
			a = "0";
			b = listZero.size() + "";
			StringBuffer ret = new StringBuffer();
			ret.append(listZero.get(0));
			for (int i = 1; i < listZero.size(); i++) {
				ret.append(' ');
				ret.append(listZero.get(i));
			}
			c = ret.toString();
		} else {
			if ((l % 2) != 0)
				l++;
			a = 1 + "";
			b = 2 + "";
			c = l + " " + (l + 1);
		}
		System.out.println(a + "\n" + b + "\n" + c);
	}

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

	static class InputReader {
		BufferedReader in;
		StringTokenizer st;

		public InputReader() throws IOException {
			in = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(in.readLine());

		}

		public String next() throws IOException {

			while (!st.hasMoreElements())
				st = new StringTokenizer(in.readLine());
			return st.nextToken();
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
	}
}