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 long long mod = 1e9 + 7;
const long long oo = 1e18;
const long long N = 6e3 + 10;
struct book {
  long long a1, a2, a3, mask1, mask2;
} mask[60][10][10];
long long l, r, k, ans = oo;
long long f[60][10][10];
vector<long long> trace;
bool check(long long pos, long long a1, long long a2, long long a3,
           long long mask1, long long mask2) {
  if (!(mask1 & 1) && (l & (1ll << pos)) && a1 == 0) return false;
  if (!(mask1 & 2) && (l & (1ll << pos)) && a2 == 0) return false;
  if (!(mask1 & 4) && (l & (1ll << pos)) && a3 == 0) return false;
  if (!(mask2 & 1) && !(r & (1ll << pos)) && a1 == 1) return false;
  if (!(mask2 & 2) && !(r & (1ll << pos)) && a2 == 1) return false;
  if (!(mask2 & 4) && !(r & (1ll << pos)) && a3 == 1) return false;
  return true;
}
void Remask(long long pos, long long m1, long long m2) {
  ans = 0;
  trace.clear();
  long long a1 = 0, a2 = 0, a3 = 0;
  while (mask[pos][m1][m2].a1 != -1) {
    a1 += ((1ll << pos) * mask[pos][m1][m2].a1);
    a2 += ((1ll << pos) * mask[pos][m1][m2].a2);
    a3 += ((1ll << pos) * mask[pos][m1][m2].a3);
    long long t1 = mask[pos][m1][m2].mask1;
    long long t2 = mask[pos][m1][m2].mask2;
    m1 = t1;
    m2 = t2;
    pos++;
  }
  trace.push_back(a1);
  trace.push_back(a2), trace.push_back(a3);
}
void solve() {
  ans = 1;
  if (l % 2 == 1) {
    trace.push_back(l + 1);
    trace.push_back(l + 2);
  } else
    trace.push_back(l), trace.push_back(l + 1);
  for (long long i = 0; i <= 45; ++i)
    for (long long j = 0; j <= 8; ++j)
      for (long long t = 0; t <= 8; ++t) {
        f[i][j][t] = oo;
        mask[i][j][t].a1 = -1;
      }
  f[45][0][0] = 0;
  for (long long i = 45; i >= 1; --i)
    for (long long j = 0; j < 8; ++j)
      for (long long t = 0; t < 8; ++t)
        if (f[i][j][t] < oo) {
          for (long long a1 = 0; a1 <= 1; ++a1)
            for (long long a2 = 0; a2 <= 1; ++a2)
              for (long long a3 = 0; a3 <= 1; ++a3) {
                if (check(i - 1, a1, a2, a3, j, t) == false) continue;
                long long mask1 = j;
                if (a1 == 1 && !(l & (1ll << (i - 1)))) mask1 |= 1;
                if (a2 == 1 && !(l & (1ll << (i - 1)))) mask1 |= 2;
                if (a3 == 1 && !(l & (1ll << (i - 1)))) mask1 |= 4;
                long long mask2 = t;
                if (a1 == 0 && (r & (1ll << (i - 1)))) mask2 |= 1;
                if (a2 == 0 && (r & (1ll << (i - 1)))) mask2 |= 2;
                if (a3 == 0 && (r & (1ll << (i - 1)))) mask2 |= 4;
                if (f[i - 1][mask1][mask2] >
                    f[i][j][t] + (a1 ^ a2 ^ a3) * (1ll << (i - 1))) {
                  f[i - 1][mask1][mask2] =
                      f[i][j][t] + (a1 ^ a2 ^ a3) * (1ll << (i - 1));
                  mask[i - 1][mask1][mask2] = {a1, a2, a3, j, t};
                }
              }
        }
  for (long long i = 0; i <= 7; ++i)
    for (long long j = 0; j <= 7; ++j) {
      if (f[0][i][j] == 0) {
        Remask(0, i, j);
        return;
      }
    }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin.tie(0);
  cin >> l >> r >> k;
  if (k == 1) {
    ans = l;
    trace.push_back(l);
  } else if (k == 2) {
    if (l % 2 == 1 && l == r - 1) {
      if (l < (l ^ r))
        ans = l, trace.push_back(l);
      else
        ans = (l ^ r), trace.push_back(l), trace.push_back(r);
    } else {
      if (l % 2 == 1) l++;
      ans = 1;
      trace.push_back(l);
      trace.push_back(l + 1);
    }
  } else if (k >= 4) {
    if (r - l + 1 == 4) solve();
    if (ans) {
      trace.clear();
      ans = 1;
      if (l % 2 == 1) l++;
      trace.push_back(l);
      trace.push_back(l + 1);
      long long tmp = 0;
      for (long long cnt = 0; cnt < 4 && l + cnt <= r; ++cnt) tmp ^= (l + cnt);
      if (ans > tmp) {
        ans = tmp;
        trace.clear();
        for (long long i = 0; i <= 3; ++i) trace.push_back(l + i);
      }
    }
  } else
    solve();
  cout << ans << '\n' << trace.size() << '\n';
  for (long long v : trace) cout << v << ' ';
}