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>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) {
    if (i != v.begin()) os << ", ";
    os << *i;
  }
  os << "]";
  return os;
}
int main() {
  long long el, r, k;
  cin >> el >> r >> k;
  vector<long long> R;
  R.push_back(el);
  long long res = el;
  if (k == 3) {
    for (int q = 0; q < (int)(50); ++q) {
      long long t = 1ll << (q + 1);
      long long x = t - 1;
      long long y = t + t - 1 - t / 2;
      long long z = t + t / 2;
      assert((x ^ y ^ z) == 0);
      if (el <= x && z <= r) {
        res = 0;
        R.clear();
        R.push_back(x);
        R.push_back(y);
        R.push_back(z);
        break;
      }
    }
  }
  if (r - el + 1 > 5) r = el + 4;
  vector<long long> A;
  for (long long i = el; i <= r; ++i) A.push_back(i);
  for (int x = 0; x < (int)(1 << ((int)((A).size()))); ++x) {
    long long score = 0;
    vector<long long> T;
    for (int i = 0; i < (int)(((int)((A).size()))); ++i)
      if (x & (1 << i)) {
        T.push_back(A[i]);
        score ^= A[i];
      }
    if (1 <= ((int)((T).size())) && ((int)((T).size())) <= k && score < res) {
      R = T;
      res = score;
    }
  }
  cout << res << endl << ((int)((R).size())) << endl;
  for (int i = 0; i < (int)(((int)((R).size()))); ++i) {
    if (i > 0) cout << " ";
    cout << R[i];
  }
  cout << endl;
}