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;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
const int INF = 1000000000;
const long long LINF = (long long)INF * (long long)INF;
vector<long long> vec;
long long l, r, k;
pair<long long, int> f(int pos, long long x, int t, int s) {
  if (t < 0) return pair<long long, int>(LINF, 0);
  if (pos == int((vec).size()))
    return (t == k ? pair<long long, int>(LINF, 0)
                   : pair<long long, int>(x, s));
  return min(f(pos + 1, x, t, s),
             f(pos + 1, x ^ vec[pos], t - 1, s | (1 << pos)));
}
int main() {
  while (cin >> l >> r >> k) {
    long long res = LINF;
    vector<long long> sol;
    if ((r - l + 1) >= 8) {
      if (k >= 4) {
        long long x = l;
        while (x % 4) x++;
        for (int i = 0; i < 4; ++i) sol.push_back(x + i);
        res = 0;
      } else if (k == 3) {
        long long pot2 = 1;
        while (pot2 <= l) pot2 <<= 1;
        long long tmp = pot2 + pot2 / 2;
        if (tmp > r) {
          long long x = l;
          while (x % 4 != 2) x++;
          for (int i = 0; i < 2; ++i) sol.push_back(x + i);
          res = 1;
        } else {
          res = 0;
          sol.push_back(pot2 + pot2 / 2);
          sol.push_back(pot2 + pot2 / 2 - 1);
          sol.push_back(pot2 - 1);
        }
      } else if (k == 2) {
        long long x = l;
        while (x % 4 != 2) x++;
        for (int i = 0; i < 2; ++i) sol.push_back(x + i);
        res = 1;
      } else {
        sol.push_back(l);
        res = l;
      }
    } else {
      vec.clear();
      for (long long i = l; i <= r; i++) vec.push_back(i);
      pair<long long, int> val = f(0, 0, k, 0);
      int aux = val.second;
      res = val.first;
      for (int i = 0; i < int((vec).size()); ++i) {
        if (aux & (1 << i)) sol.push_back(vec[i]);
      }
    }
    cout << res << endl;
    cout << int((sol).size()) << endl;
    for (int i = 0; i < int((sol).size()); ++i) {
      if (i) cout << " ";
      cout << sol[i];
    }
    cout << endl;
  }
}