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 <class T>
inline T sqr(T x) {
  return x * x;
}
const int inf = ~0u >> 1;
const double eps = 1e-8;
const double pi = acos(-1.0);
int sgn(double x) { return fabs(x) < eps ? 0 : x < -eps ? -1 : 1; }
int main() {
  long long l, r;
  int k;
  while (cin >> l >> r >> k) {
    if (k >= 4) {
      if (r - l >= 4) {
        if (l % 2 == 0) {
          cout << "0\n4\n";
          for (int i = 0; i < 4; i++) {
            cout << l + i << (i == 3 ? '\n' : ' ');
          }
        } else {
          cout << "0\n4\n";
          for (int i = 0; i < 4; i++) {
            cout << l + i + 1 << (i == 3 ? '\n' : ' ');
          }
        }
      } else {
        if (l % 2 == 0) {
          cout << "0\n4\n";
          for (int i = 0; i < 4; i++) {
            cout << l + i << (i == 3 ? '\n' : ' ');
          }
        } else {
          goto gao;
        }
      }
    } else if (k == 3) {
    gao:
      bool flag = false;
      long long a = 3ll, b = 5ll, c = 6ll;
      if (r - l <= 10000ll) {
        for (long long i = l; i < r; i++) {
          long long t = i ^ (i + 1);
          if (l <= t && t <= r) {
            a = i;
            b = i + 1;
            c = t;
            flag = true;
            break;
          }
        }
      } else {
        while (c <= r) {
          if (l <= a && a <= r && l <= b && b <= r && l <= c && c <= r) {
            flag = true;
            break;
          }
          a = (a << 1) + 1;
          b = (b << 1) + 1;
          c = (c << 1);
        }
      }
      if (flag) {
        cout << "0\n3\n";
        cout << a << ' ' << b << ' ' << c << '\n';
      } else {
        cout << "1\n2\n";
        if (l % 2 == 0) {
          cout << l << ' ' << l + 1 << '\n';
        } else {
          cout << l + 1 << ' ' << l + 2 << '\n';
        }
      }
    } else if (k == 2) {
      if (l % 2 == 0) {
        cout << "1\n2\n";
        cout << l << ' ' << l + 1 << '\n';
      } else {
        if (r - l >= 2) {
          cout << "1\n2\n";
          cout << l + 1 << ' ' << l + 2 << '\n';
        } else {
          if ((l ^ r) > r) {
            cout << l << '\n' << 1 << '\n' << l << '\n';
          } else {
            cout << (l ^ r) << '\n' << 2 << '\n' << l << ' ' << r << '\n';
          }
        }
      }
    } else {
      cout << l << '\n' << "1\n" << l << '\n';
    }
  }
}