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;
const int INF = 1e9;
int casenum, casei;
long long l, r, k, flag, ans;
map<long long, bool> b, c;
void dfs(long long x, long long v) {
  long long t = 0;
  for (long long i = l; i <= r; i++)
    if (b[i]) t++;
  if (t > k) return;
  if (v < ans && t) {
    ans = v;
    for (long long i = l; i <= r; i++) c[i] = b[i];
  }
  if (x == r + 1) return;
  b[x] = 0;
  dfs(x + 1, v);
  b[x] = 1;
  dfs(x + 1, v ^ x);
  b[x] = 0;
}
int main() {
  while (~scanf("%lld%lld%lld", &l, &r, &k)) {
    if (k == 1) {
      printf("%lld\n", l);
      printf("1\n");
      printf("%lld\n", l);
    } else {
      flag = 0;
      if (k >= 4) {
        for (long long i = l; i + 3 <= r; i++) {
          if ((i ^ (i + 1) ^ (i + 2) ^ (i + 3)) == 0) {
            printf("0\n");
            printf("4\n");
            printf("%lld %lld %lld %lld\n", i, i + 1, i + 2, i + 3);
            flag = 1;
            break;
          }
        }
      }
      if (flag == 0 && k >= 4) {
        ans = 1e18;
        b.clear();
        c.clear();
        dfs(l, 0);
        long long t = 0;
        for (long long i = l; i <= r; i++)
          if (c[i]) t++;
        printf("%lld\n", ans);
        printf("%lld\n", t);
        for (long long i = l; i <= r; i++) {
          if (c[i]) printf("%lld ", i);
        }
        printf("\n");
      } else if (flag == 0 && k == 3) {
        long long x = l, t = -1;
        while (x) {
          ++t;
          x >>= 1;
        }
        x = l;
        long long y = (1LL << (t + 1)) + (1LL << t);
        if (y <= r) {
          flag = 1;
          printf("0\n3\n%lld %lld %lld\n", x, y, x ^ y);
        }
        if (!flag) {
          for (long long i = l; i < r; i++) {
            if ((i ^ (i + 1)) == 1) {
              printf("1\n2\n%lld %lld\n", i, i + 1);
              flag = 1;
              break;
            }
          }
        }
        if (!flag) {
          if ((l ^ (l + 1)) < l) {
            printf("%lld\n2\n%lld %lld\n", l ^ (l + 1), l, l + 1);
          } else {
            printf("%lld\n1\n%lld\n", l, l);
          }
        }
      } else if (flag == 0 && k == 2) {
        for (long long i = l; i < r; i++) {
          if ((i ^ (i + 1)) == 1) {
            printf("1\n2\n%lld %lld\n", i, i + 1);
            flag = 1;
            break;
          }
        }
        if (!flag) {
          long long tmp = l ^ (l + 1);
          if (tmp < l) {
            printf("%lld\n2\n%lld %lld\n", l ^ (l + 1), l, l + 1);
          } else {
            printf("%lld\n1\n%lld\n", l, l);
          }
        }
      }
    }
  }
  return 0;
}