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 long long INF = 1ll << 60;
const int N = 10;
int sz;
long long path[N], ans[N], minxor;
void Dfs(long long pos, long long bound, int used, int limit,
         long long xorval) {
  if (used > limit) return;
  if (used > 0 && xorval < minxor) {
    minxor = xorval;
    sz = used;
    memcpy(ans + 1, path + 1, sizeof(long long) * sz);
  }
  for (long long next = pos + 1; next <= bound; next++) {
    path[used + 1] = next;
    Dfs(next, bound, used + 1, limit, xorval ^ next);
  }
}
int main() {
  long long l, r, k;
  cin >> l >> r >> k;
  if (r - l <= 4) {
    minxor = INF;
    Dfs(l - 1, r, 0, k, 0);
    cout << minxor << endl << sz << endl;
    for (int i = 1; i <= sz; i++) {
      if (i > 1) cout << ' ';
      cout << ans[i];
    }
    cout << endl;
    return 0;
  }
  if (k == 1)
    cout << l << endl << 1 << endl << l << endl;
  else if (k == 2) {
    cout << 1 << endl << 2 << endl;
    if (l % 2 == 0)
      cout << l << ' ' << l + 1 << endl;
    else
      cout << l + 1 << ' ' << l + 2 << endl;
  } else if (k >= 4) {
    cout << 0 << endl << 4 << endl;
    if (l % 2 == 0)
      cout << l << ' ' << l + 1 << ' ' << l + 2 << ' ' << l + 3 << endl;
    else
      cout << l + 1 << ' ' << l + 2 << ' ' << l + 3 << ' ' << l + 4 << endl;
  } else {
    for (int b = 1;; b++) {
      if ((1ll << b) > r) break;
      if ((1ll << b) > l && (1ll << b) + (1ll << b - 1) <= r) {
        cout << 0 << endl << 3 << endl;
        cout << (1ll << b) - 1 << ' ' << (1ll << b) + (1ll << b - 1) - 1 << ' '
             << (1ll << b) + (1ll << b - 1) << endl;
        return 0;
      }
    }
    cout << 1 << endl << 2 << endl;
    if (l % 2 == 0)
      cout << l << ' ' << l + 1 << endl;
    else
      cout << l + 1 << ' ' << l + 2 << endl;
  }
  return 0;
}