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;
template <typename T, typename U>
inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void amax(T &x, U y) {
  if (x < y) x = y;
}
long long L, R;
int K;
long long memo[42][1 << 3][1 << 3][1 << 3];
vector<long long> hukugen;
long long rec(int i, int lt, int gt, int eq) {
  long long &x = memo[i + 1][lt][gt][eq];
  if (x != -1) return x;
  if (i == -1) return eq == 0 ? 0 : 0x3f3f3f3f3f3f3f3fLL;
  x = 0x3f3f3f3f3f3f3f3fLL;
  int l = L >> i & 1, r = R >> i & 1;
  for (int(j) = 0; (j) < (int)(1 << K); ++(j)) {
    bool ok = true;
    int nlt = lt, ngt = gt;
    for (int(k) = 0; (k) < (int)(K); ++(k)) {
      ok &= (lt >> k & 1) || (j >> k & 1) <= r;
      ok &= (gt >> k & 1) || l <= (j >> k & 1);
      nlt |= ((j >> k & 1) < r) << k;
      ngt |= (l < (j >> k & 1)) << k;
    }
    if (!ok) continue;
    int neq = eq & (((j >> 0 & 1) == (j >> 1 & 1)) << 0 |
                    ((j >> 0 & 1) == (j >> 2 & 1)) << 1 |
                    ((j >> 1 & 1) == (j >> 2 & 1)) << 2);
    int y = 0;
    for (int(k) = 0; (k) < (int)(K); ++(k)) y ^= j >> k & 1;
    amin(x, rec(i - 1, nlt, ngt, neq) | ((long long)y << i));
  }
  return x;
}
void rec_hukugen(int i, int lt, int gt, int eq) {
  if (i == -1) {
    assert(eq == 0);
    return;
  }
  long long x = memo[i + 1][lt][gt][eq];
  int l = L >> i & 1, r = R >> i & 1;
  for (int(j) = 0; (j) < (int)(1 << K); ++(j)) {
    bool ok = true;
    int nlt = lt, ngt = gt;
    for (int(k) = 0; (k) < (int)(K); ++(k)) {
      ok &= (lt >> k & 1) || (j >> k & 1) <= r;
      ok &= (gt >> k & 1) || l <= (j >> k & 1);
      nlt |= ((j >> k & 1) < r) << k;
      ngt |= (l < (j >> k & 1)) << k;
    }
    if (!ok) continue;
    int neq = eq & (((j >> 0 & 1) == (j >> 1 & 1)) << 0 |
                    ((j >> 0 & 1) == (j >> 2 & 1)) << 1 |
                    ((j >> 1 & 1) == (j >> 2 & 1)) << 2);
    int y = 0;
    for (int(k) = 0; (k) < (int)(K); ++(k)) y ^= j >> k & 1;
    long long nx = rec(i - 1, nlt, ngt, neq) | ((long long)y << i);
    if (nx == x) {
      for (int(k) = 0; (k) < (int)(K); ++(k))
        hukugen[k] |= (long long)(j >> k & 1) << i;
      return rec_hukugen(i - 1, nlt, ngt, neq);
    }
  }
  assert(false);
}
int main() {
  long long l, r;
  int k;
  cin >> l >> r >> k;
  vector<long long> ans;
  long long ansxor;
  if (k >= 4 && r - (l + (l % 2 == 1)) + 1 >= 4) {
    for (int(i) = 0; (i) < (int)(4); ++(i)) ans.push_back(l + (l % 2 == 1) + i);
    ansxor = 0;
  } else if (k == 4) {
    assert(l % 2 == 1 && r - l + 1 == 4);
    pair<long long, int> p(0x3f3f3f3f3f3f3f3fLL, -1);
    for (int(i) = 0; (i) < (int)(1 << 4); ++(i))
      if (i != 0) {
        long long x = 0;
        for (int(j) = 0; (j) < (int)(4); ++(j))
          if (i >> j & 1) x ^= l + j;
        amin(p, make_pair((x), (i)));
      }
    for (int(j) = 0; (j) < (int)(4); ++(j))
      if (p.second >> j & 1) ans.push_back(l + j);
    ansxor = p.first;
  } else {
    L = l, R = r;
    ansxor = 0x3f3f3f3f3f3f3f3fLL;
    for (K = 1; K <= k; ++K) {
      memset(memo, -1, sizeof(memo));
      long long x = rec(40, 0, 0, (1 << K) - 1);
      if (ansxor > x) {
        ansxor = x;
        hukugen.assign(K, 0);
        rec_hukugen(40, 0, 0, (1 << K) - 1);
        ans = hukugen;
      }
    }
  }
  sort((ans).begin(), (ans).end());
  assert(ans.size() <= k);
  assert(unique((ans).begin(), (ans).end()) == ans.end());
  long long x = 0;
  for (int(i) = 0; (i) < (int)(ans.size()); ++(i)) x ^= ans[i];
  assert(x == ansxor);
  cout << x << endl;
  cout << ans.size() << endl;
  for (int(i) = 0; (i) < (int)(ans.size()); ++(i)) {
    if (i != 0) cout << ' ';
    cout << ans[i];
  }
  cout << endl;
  return 0;
}