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

public class D {

  private void solve() throws IOException {
    long l = nl();
    long r = nl();
    long k = nl();

    if (k == 3) {
      long mp = p2(l);
      long a = (mp - 1);
      long b = (a ^ (mp >> 1) ^ mp);
      long c = mp ^ (mp >> 1);
      if ((c <= r && c >= l) && (a <= r && a >= l) && (b >= l && b <= r)) {
        prln(0);
        prln(3);
        pr(a + " " + b + " " + c);
        return;
      }
    }

    List<Long> vals = new ArrayList<Long>();
    List<Long> ans = null;
    int t = 0;
    for (long v = l; v <= r && t < 20; ++v, ++t)
      vals.add(v);

    Long[] arr = vals.toArray(new Long[1]);

    long min = Long.MAX_VALUE;
    int ptr = 1 << arr.length;
    for (int i = 1; i != ptr; ++i) {
      long cnd = 0;
      if (Integer.bitCount(i) > k) continue;
      for (int p = 1, idx = 0; p != ptr; p <<= 1, idx++) {
        if ((p & i) != 0) {
          cnd ^= arr[idx];
        }
      }
      if (cnd < min) {
        min = cnd;
        ans = new ArrayList<Long>();
        for (int p = 1, idx = 0; p != ptr; p <<= 1, idx++) {
          if ((p & i) != 0) {
            ans.add(arr[idx]);
          }
        }
      }
    }

    prln(min);
    prln(ans.size());
    for (Long ll : ans) pr(ll + " ");
  }

  long p2(long t) {
    long res = 1;
    while (res <= t) {
      res <<= 1;
    }
    return res;
  }

  public static void main(String ... args) throws IOException { new D().run(); }

  private PrintWriter pw;
  private BufferedReader br;
  private StringTokenizer st;

  private void run() throws IOException {
    pw = new PrintWriter(System.out);
    br = new BufferedReader(new InputStreamReader(System.in));
    solve();
    br.close();
    pw.close();
  }

  private void pr(Object o) { pw.print(o); }
  private void prln(Object o) {pw.println(o);}
  private void prln() {pw.println();}

  private long nl() throws IOException { return Long.parseLong(nt());   }

  private double nd() throws IOException  { return Double.parseDouble(nt()); }

  private int ni()throws IOException  { return Integer.parseInt(nt()); }

  private String nt() throws IOException {
    if (st == null || !st.hasMoreTokens())
      st = new StringTokenizer(br.readLine());
    return st.nextToken();
  }
}