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>
T sqr(T x) {
  return x * x;
}
inline int getBit(long long x, int pos) { return ((x >> pos) & 1); }
const double eps = 1e-9;
const double pi = acos(-1.0);
int dp[45][4][4][4];
int pr[45][4][4][4];
bool doIt(long long lf, long long rg) {
  dp[0][0][0][0] = 1;
  for (int i = 0; i < 44; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        for (int t = 0; t < 4; t++) {
          if (dp[i][j][k][t] == 1) {
            for (int msk = 0; msk < 4; msk++) {
              int a = msk & 1;
              int b = (msk >> 1) & 1;
              int c = a ^ b;
              int j1 = 0;
              if (j & 1) {
                if (getBit(lf, i) == 1) {
                  if (a == 1) j1 |= 1;
                } else {
                  j1 |= 1;
                }
              } else {
                if (getBit(lf, i) == 0) {
                  if (a == 1) j1 |= 1;
                }
              }
              if ((j >> 1) & 1) {
                if (getBit(rg, i) == 1) {
                  if (a == 1) j1 |= 2;
                } else {
                  j1 |= 2;
                }
              } else {
                if (getBit(rg, i) == 0) {
                  if (a == 1) j1 |= 2;
                }
              }
              int k1 = 0;
              if (k & 1) {
                if (getBit(lf, i) == 1) {
                  if (b == 1) k1 |= 1;
                } else {
                  k1 |= 1;
                }
              } else {
                if (getBit(lf, i) == 0) {
                  if (b == 1) k1 |= 1;
                }
              }
              if ((k >> 1) & 1) {
                if (getBit(rg, i) == 1) {
                  if (b == 1) k1 |= 2;
                } else {
                  k1 |= 2;
                }
              } else {
                if (getBit(rg, i) == 0) {
                  if (b == 1) k1 |= 2;
                }
              }
              int t1 = 0;
              if (t & 1) {
                if (getBit(lf, i) == 1) {
                  if (c == 1) t1 |= 1;
                } else {
                  t1 |= 1;
                }
              } else {
                if (getBit(lf, i) == 0) {
                  if (c == 1) t1 |= 1;
                }
              }
              if ((t >> 1) & 1) {
                if (getBit(rg, i) == 1) {
                  if (c == 1) t1 |= 2;
                } else {
                  t1 |= 2;
                }
              } else {
                if (getBit(rg, i) == 0) {
                  if (c == 1) t1 |= 2;
                }
              }
              dp[i + 1][j1][k1][t1] = 1;
              pr[i + 1][j1][k1][t1] =
                  ((((((j << 2) | k) << 2) | t) << 2) | msk);
            }
          }
        }
      }
    }
  }
  if (dp[44][1][1][1] == 0) return false;
  long long a = 0, b = 0, c = 0;
  int i = 44, j = 1, k = 1, t = 1;
  while (i > 0) {
    a <<= 1;
    b <<= 1;
    c <<= 1;
    int A = pr[i][j][k][t] & 1;
    int B = (pr[i][j][k][t] >> 1) & 1;
    a += A;
    b += B;
    c += (A ^ B);
    pr[i][j][k][t] >>= 2;
    int nt = (pr[i][j][k][t] & 3);
    pr[i][j][k][t] >>= 2;
    int nk = (pr[i][j][k][t] & 3);
    pr[i][j][k][t] >>= 2;
    int nj = (pr[i][j][k][t] & 3);
    --i;
    t = nt;
    k = nk;
    j = nj;
  }
  cout << 0 << endl;
  cout << 3 << endl;
  cout << a << " " << b << " " << c << endl;
  return true;
}
long long lf, rg;
int k;
int main() {
  cin >> lf >> rg >> k;
  if (k == 1) {
    cout << lf << endl;
    cout << 1 << endl << lf << endl;
    return 0;
  }
  if (rg - lf + 1 < 15) {
    int bstMask = 1;
    long long res = lf;
    for (int mask = 1; mask < (1 << (rg - lf + 1)); mask++) {
      long long cur = 0;
      int cnt = 0;
      for (int i = 0; i < (rg - lf + 1); i++) {
        if (getBit(mask, i) == 1) {
          cur ^= (lf + i);
          cnt++;
        }
      }
      if (cnt <= k && cur < res) {
        res = cur;
        bstMask = mask;
      }
    }
    cout << res << endl;
    int cnt = 0;
    int tmp = bstMask;
    while (tmp > 0) {
      cnt += (tmp & 1);
      tmp >>= 1;
    }
    cout << cnt << endl;
    for (int i = 0; i < (rg - lf + 1); i++) {
      if (getBit(bstMask, i)) {
        cout << lf + i << " ";
      }
    }
    return 0;
  }
  if (k >= 4) {
    cout << 0 << endl;
    cout << 4 << endl;
    long long a = (lf + 1) / 2;
    a *= 2;
    for (int i = 0; i < 4; i++) cout << a + i << " ";
    cout << endl;
  } else {
    if (k == 3) {
      if (doIt(lf - 1, rg)) return 0;
    }
    cout << 1 << endl;
    cout << 2 << endl;
    long long a = (lf + 1) / 2;
    a *= 2;
    cout << a << " " << a + 1 << endl;
  }
  return 0;
}