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 modul = 1000000007;
const int nmax = 1010;
const double e = 1e-8;
const double pi = acos(-1);
int n, m, stest, k;
long long l, r, res;
vector<long long> ans;
string a, b;
bool kq[60][nmax], F[60][nmax];
string make(long long u) {
  string v = "";
  while (u) {
    v = (char)(u % 2 + '0') + v;
    u /= 2;
  }
  return v;
}
bool Cal(int i, int s, long long x, long long y, long long z) {
  if (i == n) {
    if (x != y && y != z && z != x) {
      F[i][s] = true;
      return true;
    }
    F[i][s] = false;
    return false;
  }
  if (kq[i][s]) return F[i][s];
  kq[i][s] = true;
  F[i][s] = false;
  int a1, b1, a2, b2, a3, b3;
  if (((s & (1 << 8)) > 0) == 0)
    a1 = a[i] - '0';
  else
    a1 = 0;
  if (((s & (1 << 7)) > 0) == 0)
    b1 = b[i] - '0';
  else
    b1 = 1;
  if (((s & (1 << 6)) > 0) == 0)
    a2 = a[i] - '0';
  else
    a2 = 0;
  if (((s & (1 << 5)) > 0) == 0)
    b2 = b[i] - '0';
  else
    b2 = 1;
  if (((s & (1 << 4)) > 0) == 0)
    a3 = a[i] - '0';
  else
    a3 = 0;
  if (((s & (1 << 3)) > 0) == 0)
    b3 = b[i] - '0';
  else
    b3 = 1;
  for (int xx = a1; xx <= b1; xx++)
    for (int yy = a2; yy <= b2; yy++)
      for (int zz = a3; zz <= b3; zz++)
        if ((xx ^ yy ^ zz) == 0) {
          int ss = s;
          ss |= (1 << 8) * (((s & (1 << 8)) > 0) | (xx != a[i] - '0'));
          ss |= (1 << 7) * (((s & (1 << 7)) > 0) | (xx != b[i] - '0'));
          ss |= (1 << 6) * (((s & (1 << 6)) > 0) | (yy != a[i] - '0'));
          ss |= (1 << 5) * (((s & (1 << 5)) > 0) | (yy != b[i] - '0'));
          ss |= (1 << 4) * (((s & (1 << 4)) > 0) | (zz != a[i] - '0'));
          ss |= (1 << 3) * (((s & (1 << 3)) > 0) | (zz != b[i] - '0'));
          ss |= (1 << 2) * (((s & (1 << 2)) > 0) | (xx != yy));
          ss |= (1 << 1) * (((s & (1 << 1)) > 0) | (yy != zz));
          ss |= (1 << 0) * (((s & (1 << 0)) > 0) | (xx != zz));
          if (Cal(i + 1, ss, x * 2 + xx, y * 2 + yy, z * 2 + zz))
            F[i][s] = true;
        }
  return F[i][s];
}
void Trace(int i, int s, long long x, long long y, long long z) {
  if (i == n) {
    if (x != y && y != z && z != x) {
      res = 0;
      ans.clear();
      ans.push_back(x);
      ans.push_back(y);
      ans.push_back(z);
    }
    return;
  }
  int a1, b1, a2, b2, a3, b3;
  if (((s & (1 << 8)) > 0) == 0)
    a1 = a[i] - '0';
  else
    a1 = 0;
  if (((s & (1 << 7)) > 0) == 0)
    b1 = b[i] - '0';
  else
    b1 = 1;
  if (((s & (1 << 6)) > 0) == 0)
    a2 = a[i] - '0';
  else
    a2 = 0;
  if (((s & (1 << 5)) > 0) == 0)
    b2 = b[i] - '0';
  else
    b2 = 1;
  if (((s & (1 << 4)) > 0) == 0)
    a3 = a[i] - '0';
  else
    a3 = 0;
  if (((s & (1 << 3)) > 0) == 0)
    b3 = b[i] - '0';
  else
    b3 = 1;
  for (int xx = a1; xx <= b1; xx++)
    for (int yy = a2; yy <= b2; yy++)
      for (int zz = a3; zz <= b3; zz++)
        if ((xx ^ yy ^ zz) == 0) {
          int ss = s;
          ss |= (1 << 8) * (((s & (1 << 8)) > 0) | (xx != a[i] - '0'));
          ss |= (1 << 7) * (((s & (1 << 7)) > 0) | (xx != b[i] - '0'));
          ss |= (1 << 6) * (((s & (1 << 6)) > 0) | (yy != a[i] - '0'));
          ss |= (1 << 5) * (((s & (1 << 5)) > 0) | (yy != b[i] - '0'));
          ss |= (1 << 4) * (((s & (1 << 4)) > 0) | (zz != a[i] - '0'));
          ss |= (1 << 3) * (((s & (1 << 3)) > 0) | (zz != b[i] - '0'));
          ss |= (1 << 2) * (((s & (1 << 2)) > 0) | (xx != yy));
          ss |= (1 << 1) * (((s & (1 << 1)) > 0) | (yy != zz));
          ss |= (1 << 0) * (((s & (1 << 0)) > 0) | (xx != zz));
          if (F[i + 1][ss]) {
            Trace(i + 1, ss, x * 2 + xx, y * 2 + yy, z * 2 + zz);
            return;
          }
        }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> l >> r >> k;
  if (k >= 4 && r - l + 1 >= 5) {
    cout << 0 << endl;
    cout << 4 << endl;
    if (l % 2 == 1) l++;
    cout << l << " " << l + 1 << " " << l + 2 << " " << l + 3 << endl;
    return 0;
  }
  res = l;
  ans.push_back(l);
  if (k >= 2) {
    if (res > (l ^ (l + 1))) {
      res = (l ^ (l + 1));
      ans.clear();
      ans.push_back(l);
      ans.push_back(l + 1);
    }
    if (l + 2 <= r && res > ((l + 1) ^ (l + 2))) {
      res = (l + 1) ^ (l + 2);
      ans.clear();
      ans.push_back(l + 1);
      ans.push_back(l + 2);
    }
  }
  if (k >= 3) {
    a = make(l);
    b = make(r);
    n = (int)b.size();
    while ((int)a.size() < n) a = '0' + a;
    Cal(0, 0, 0, 0, 0);
    if (F[0][0]) Trace(0, 0, 0, 0, 0);
  }
  if (k >= 4) {
    if (res > (l ^ (l + 1) ^ (l + 2) ^ (l + 3))) {
      res = (l ^ (l + 1) ^ (l + 2) ^ (l + 3));
      ans.clear();
      ans.push_back(l);
      ans.push_back(l + 1);
      ans.push_back(l + 2);
      ans.push_back(l + 3);
    }
  }
  cout << res << endl;
  cout << (int)ans.size() << endl;
  for (int i = 0; i <= (int)ans.size() - 1; i++) cout << ans[i] << " ";
  return 0;
}