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;
vector<long long> res;
void add(long long t) { res.push_back(t); }
int main() {
  cin.sync_with_stdio(0);
  cout.setf(ios::floatfield, ios::fixed);
  cout.precision(8);
  long long l, r, k;
  cin >> l >> r >> k;
  if (k == 1) {
    add(l);
  } else if (k == 2) {
    if (r - l + 1 == 2) {
      if ((l ^ r) < l) {
        add(l);
        add(r);
      } else {
        add(l);
      }
    } else {
      long long even = l;
      if (even % 2) ++even;
      add(even);
      add(even + 1);
    }
  } else {
    long long t = l;
    int len = 0;
    while (t) {
      ++len;
      t >>= 1;
    }
    long long even = l;
    if (even % 2) ++even;
    add(even);
    add(even + 1);
    long long one = (1LL << len) | (l & (1LL << (len - 1))), second = l ^ one;
    if (one <= r && second <= r) {
      res.clear();
      add(l);
      add(one);
      add(second);
    }
    long long st = l;
    if (k >= 4 && st + 3 <= r) {
      for (int ad = 0; ad < 4 && st + 3 <= r; ++ad, ++st) {
        long long s = 0;
        for (int i = 0; i < 4; ++i) {
          s ^= st + i;
        }
        if (!s) {
          res.clear();
          add(st);
          add(st + 1);
          add(st + 2);
          add(st + 3);
          break;
        }
      }
    }
  }
  long long sum = 0;
  for (int i = 0; i < res.size(); ++i) {
    sum ^= res[i];
  }
  cout << sum << endl;
  cout << res.size() << endl;
  for (int i = 0; i < res.size(); ++i) {
    cout << res[i] << " ";
  }
  cout << endl;
  return 0;
}