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;
template <class T>
inline const T gcd(T& a, T& b) {
  return __gcd(a, b);
};
template <class T>
inline const T lcm(T& a, T& b) {
  return a * (b / gcd<T>(a, b));
};
void load(vector<int>& tab) {
  for (int i = 0; i < int(tab.size()); ++i) {
    scanf("%d", &tab[i]);
  }
}
void load(vector<char>& tab) {
  for (int i = 0; i < int(tab.size()); ++i) {
    scanf(" %c", &tab[i]);
  }
}
void load(vector<long long>& tab) {
  for (int i = 0; i < int(tab.size()); ++i) {
    scanf("%lld", &tab[i]);
  }
}
template <typename T>
T StringToNumber(const string& Text) {
  stringstream ss(Text);
  T result;
  return ss >> result ? result : 0;
}
long long pow_mod(long long a, long long b, long long mod) {
  long long res = 1, x = a % mod;
  for (long long i = 1; i <= b; i <<= 1) {
    x %= mod;
    if (b & i) {
      res *= x;
      res %= mod;
    }
    x *= x;
  }
  return res;
}
void brute(long long l, long long r, long long k) {
  long long ans = LLONG_MAX;
  vector<long long> ns;
  for (int i = 1; i <= (1 << (r - l + 1)); i++) {
    long long res = 0;
    long long tmp = i;
    long long cnt = 0;
    vector<long long> arr;
    long long kcnt = 0;
    while (tmp > 0) {
      if (tmp % 2) {
        res ^= (l + cnt);
        arr.push_back(l + cnt);
        kcnt++;
      }
      cnt++;
      tmp /= 2;
    }
    if (ans > res && kcnt <= k) {
      ns = arr;
      ans = res;
    }
  }
  cout << ans << endl;
  cout << ns.size() << endl;
  for (int i = 0; i < int(ns.size()); i++) {
    cout << ns[i] << " ";
  }
  cout << endl;
}
void solve3(long long a, long long b, long long k) {
  long long mn = 1;
  long long mx = 3;
  while (mx <= b) {
    if (mn >= a) {
      cout << 0 << endl;
      cout << 3 << endl;
      cout << mn << " " << mx - 1 << " " << mx << endl;
      return;
    }
    mn <<= 1;
    mn++;
    mx <<= 1;
  }
  cout << 1 << endl;
  cout << 2 << endl;
  if (a & 1)
    cout << a + 1 << " " << a + 2 << endl;
  else
    cout << a << " " << a + 1 << endl;
  return;
}
void solve(long long l, long long r, long long k) {
  if (k == 1) {
    cout << l << endl;
    cout << "1" << endl;
    cout << l << endl;
    return;
  }
  if (r - l <= 4) {
    brute(l, r, k);
    return;
  }
  if (k == 2) {
    cout << "1" << endl;
    cout << "2" << endl;
    int j;
    int to;
    if (l % 2) {
      j = 1;
      to = 3;
    } else {
      j = 0;
      to = 2;
    }
    for (; j < to; j++) cout << l + j << " ";
    cout << endl;
    return;
  }
  if (k >= 4) {
    cout << "0" << endl;
    cout << "4" << endl;
    int j;
    int to;
    if (l % 2) {
      j = 1;
      to = 5;
    } else {
      j = 0;
      to = 4;
    }
    for (; j < to; j++) cout << l + j << " ";
    cout << endl;
    return;
  }
  if (k == 3) {
    solve3(l, r, k);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  long long l, r, k;
  cin >> l >> r >> k;
  solve(l, r, k);
}