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 int T = 41;
const long long X[] = {0,
                       1,
                       3,
                       7,
                       15,
                       31,
                       63,
                       127,
                       255,
                       511,
                       1023,
                       2047,
                       4095,
                       8191,
                       16383,
                       32767,
                       65535,
                       131071,
                       262143,
                       524287,
                       1048575,
                       2097151,
                       4194303,
                       8388607,
                       16777215,
                       33554431,
                       67108863,
                       134217727,
                       268435455,
                       536870911,
                       1073741823,
                       2147483647,
                       4294967295LL,
                       8589934591LL,
                       17179869183LL,
                       34359738367LL,
                       68719476735LL,
                       137438953471LL,
                       274877906943LL,
                       549755813887LL,
                       1099511627775LL};
const long long Y[] = {1,
                       2,
                       5,
                       11,
                       23,
                       47,
                       95,
                       191,
                       383,
                       767,
                       1535,
                       3071,
                       6143,
                       12287,
                       24575,
                       49151,
                       98303,
                       196607,
                       393215,
                       786431,
                       1572863,
                       3145727,
                       6291455,
                       12582911,
                       25165823,
                       50331647,
                       100663295,
                       201326591,
                       402653183,
                       805306367,
                       1610612735,
                       3221225471LL,
                       6442450943LL,
                       12884901887LL,
                       25769803775LL,
                       51539607551LL,
                       103079215103LL,
                       206158430207LL,
                       412316860415LL,
                       824633720831LL,
                       1649267441663LL};
const long long Z[] = {1,
                       3,
                       6,
                       12,
                       24,
                       48,
                       96,
                       192,
                       384,
                       768,
                       1536,
                       3072,
                       6144,
                       12288,
                       24576,
                       49152,
                       98304,
                       196608,
                       393216,
                       786432,
                       1572864,
                       3145728,
                       6291456,
                       12582912,
                       25165824,
                       50331648,
                       100663296,
                       201326592,
                       402653184,
                       805306368,
                       1610612736,
                       3221225472LL,
                       6442450944LL,
                       12884901888LL,
                       25769803776LL,
                       51539607552LL,
                       103079215104LL,
                       206158430208LL,
                       412316860416LL,
                       824633720832LL,
                       1649267441664LL};
int k;
long long l, r;
long long ans;
int tot, anstot;
long long q[10], ansq[10];
void search(long long now, long long res) {
  if (tot > k) return;
  if (now == r + 1) {
    if (tot && ans > res) {
      ans = res;
      anstot = tot;
      memcpy(ansq, q, sizeof(*q) * (tot + 1));
    }
    return;
  }
  search(now + 1, res);
  q[++tot] = now;
  search(now + 1, res ^ now);
  q[tot--] = 0;
}
void bf() {
  ans = r + 1;
  search(l, 0);
  cout << ans << endl;
  cout << anstot << endl;
  for (int i = 1; i <= anstot; ++i) {
    cout << ansq[i];
    if (i != anstot)
      cout << " ";
    else
      cout << endl;
  }
}
int main() {
  cin >> l >> r >> k;
  if (r - l + 1 <= 8) {
    bf();
  } else {
    if (k >= 4) {
      long long x = l;
      if (x & 1) ++x;
      cout << 0 << endl;
      cout << 4 << endl;
      cout << x << " " << x + 1 << " " << x + 2 << " " << x + 3 << endl;
    } else if (k == 1) {
      cout << l << endl;
      cout << 1 << endl;
      cout << l << endl;
    } else if (k == 2) {
      long long x = l;
      if (x & 1) ++x;
      cout << 1 << endl;
      cout << 2 << endl;
      cout << x << " " << x + 1 << endl;
    } else {
      bool flag = 0;
      for (int i = 0; i < T; ++i) {
        if (l <= X[i] && Z[i] <= r) {
          flag = 1;
          cout << 0 << endl;
          cout << 3 << endl;
          cout << X[i] << " " << Y[i] << " " << Z[i] << endl;
          break;
        }
      }
      if (!flag) {
        long long x = l;
        if (x & 1) ++x;
        cout << 1 << endl;
        cout << 2 << endl;
        cout << x << " " << x + 1 << endl;
      }
    }
  }
  return 0;
}