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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void brute(long long l, long long r, int k) {
  vector<long long> v(1, l);
  if (k >= 2)
    for (long long a = l; a < r; a++)
      for (long long b = a + 1; b <= r; b++) {
        long long tmp = 0;
        for (long long x : v) tmp ^= x;
        if (tmp <= (a ^ b)) continue;
        v.clear();
        v.push_back(a);
        v.push_back(b);
      }
  if (k >= 3)
    for (long long a = l; a < r; a++)
      for (long long b = a + 1; b < r; b++)
        for (long long c = b + 1; c <= r; c++) {
          long long tmp = 0;
          for (long long x : v) tmp ^= x;
          if (tmp <= (a ^ b ^ c)) continue;
          v.clear();
          v.push_back(a);
          v.push_back(b);
          v.push_back(c);
        }
  if (k >= 4)
    for (long long a = l; a < r; a++)
      for (long long b = a + 1; b < r; b++)
        for (long long c = b + 1; c < r; c++)
          for (long long d = c + 1; d <= r; d++) {
            long long tmp = 0;
            for (long long x : v) tmp ^= x;
            if (tmp <= (a ^ b ^ c ^ d)) continue;
            v.clear();
            v.push_back(a);
            v.push_back(b);
            v.push_back(c);
            v.push_back(d);
          }
  long long val = 0;
  for (long long x : v) val ^= x;
  printf("%I64d\n%d\n", val, v.size());
  for (long long x : v) printf("%I64d ", x);
}
void solve(long long l, long long r, int k) {
  if (k == 1) {
    printf("%I64d\n1\n%I64d", l, l);
    return;
  }
  if (k == 2) {
    if (l == 1) {
      printf("1\n1\n1");
      return;
    }
    long long x = l;
    if (x & 1) x++;
    printf("1\n2\n%I64d %I64d", x, x + 1);
    return;
  }
  if (k > 3) {
    long long x = l;
    if (x & 1) x++;
    printf("0\n4\n");
    for (int i = 0; i < 4; i++, x++) printf("%I64d ", x);
    return;
  }
  long long x, y;
  x = 2;
  y = 3;
  while (max(x, y) <= r) {
    long long z = x ^ y;
    if (z >= l) {
      printf("0\n3\n%I64d %I64d %I64d", x, y, z);
      return;
    }
    x = x * 2 + 1;
    y *= 2;
  }
  if (l == 1) {
    printf("1\n1\n1");
    return;
  }
  x = l;
  if (x & 1) x++;
  printf("1\n2\n%I64d %I64d", x, x + 1);
}
int main() {
  long long l, r;
  int k;
  scanf("%I64d%I64d%d", &l, &r, &k);
  if (r - l < 20)
    brute(l, r, k);
  else
    solve(l, r, k);
  return 0;
}