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>
#pragma comment(linker, "/STACK:100000000000000")
const long long int INF = 2e9 + 1;
using namespace std;
bool zero(long long int l, long long int r, long long int k) {
  if (k < 3) return false;
  int maxi = 0;
  for (int(i) = 0; (i) < (40); (i)++) {
    if ((1LL << i) & l) {
      maxi = i;
    }
  }
  if ((1LL << (maxi + 1)) <= r) {
    long long int f, s;
    s = f = (1LL << (maxi + 1));
    long long int with = l;
    for (int i = maxi; i >= 0; i--) {
      if (with & (1LL << i)) {
        if (s + (1LL << i) <= r) {
          s += (1LL << i);
          with -= (1LL << i);
        } else if (f + (1LL << i) <= r) {
          f += (1LL << i);
          with -= (1LL << i);
        }
      }
    }
    if (!with) {
      printf("0\n3\n");
      cout << l << " " << f << " " << s;
      return true;
    }
  }
  if (k < 4) return false;
  if (r - l + 1 >= 7) {
    for (; l <= r; l++) {
      if (l % 4 == 0) {
        printf("0\n4\n");
        for (int(i) = 0; (i) < (4); (i)++) cout << l + i << " ";
        return true;
      }
    }
  } else {
    for (int(i) = 0; (i) < (1 << (r - l + 1)); (i)++) {
      if (!i) continue;
      long long int xo = 0;
      vector<long long int> us;
      for (int(j) = 0; (j) < ((r - l + 1)); (j)++) {
        if (i & (1 << j)) {
          xo ^= (l + j);
          us.push_back(l + j);
        }
      }
      if (xo == 0) {
        cout << 0 << endl << (int)(us).size() << endl;
        for (int(i) = 0; (i) < ((int)(us).size()); (i)++) {
          cout << us[i] << " ";
        }
        return true;
      }
    }
  }
  return false;
}
int main() {
  long long int l, r, k;
  cin >> l >> r >> k;
  if (k == 1) {
    cout << l << endl << 1 << endl << l;
    return 0;
  }
  if (r - l == 1) {
    if ((l ^ r) < l)
      cout << (l ^ r) << endl << 2 << endl << l << " " << r;
    else
      cout << l << endl << 1 << endl << l;
    return 0;
  }
  if (!zero(l, r, k)) {
    if ((l ^ (l + 1)) != 1) l++;
    cout << 1 << endl << 2 << endl << l << " " << l + 1;
  }
}