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;
void prt(long long num) {
  for (long long i = 0; i < 45; i++) {
    if ((1ll << i) & num)
      cout << "1";
    else
      cout << "0";
  }
  cout << "\n";
}
long long l, r, k, min_ = 1e12;
long long ar[5][5];
void ff(), ss(), tt(), fo();
int main() {
  cin >> l >> r >> k;
  ff(), ss(), tt(), fo();
  long long ans1 = (ar[0][0]);
  long long ans2 = (ar[1][0] ^ ar[1][1]);
  long long ans3 = (ar[2][0] ^ ar[2][1] ^ ar[2][2]);
  long long ans4 = (ar[3][0] ^ ar[3][1] ^ ar[3][2] ^ ar[3][3]);
  if (k == 1) {
    cout << ans1 << "\n" << 1 << "\n" << ans1 << "\n";
  } else if (k == 2) {
    if (ans1 < ans2)
      cout << ans1 << "\n" << 1 << "\n" << ans1 << "\n";
    else
      cout << ans2 << "\n" << 2 << "\n" << ar[1][0] << " " << ar[1][1] << "\n";
  } else if (k == 3) {
    long long min_ = min({ans1, ans2, ans3});
    if (min_ == ans1)
      cout << ans1 << "\n" << 1 << "\n" << ans1 << "\n";
    else if (min_ == ans2)
      cout << ans2 << "\n" << 2 << "\n" << ar[1][0] << " " << ar[1][1] << "\n";
    else if (min_ == ans3)
      cout << ans3 << "\n"
           << 3 << "\n"
           << ar[2][0] << " " << ar[2][1] << " " << ar[2][2] << "\n";
  } else {
    long long min_ = min({ans1, ans2, ans3, ans4});
    if (min_ == ans1)
      cout << ans1 << "\n" << 1 << "\n" << ans1 << "\n";
    else if (min_ == ans2)
      cout << ans2 << "\n" << 2 << "\n" << ar[1][0] << " " << ar[1][1] << "\n";
    else if (min_ == ans3)
      cout << ans3 << "\n"
           << 3 << "\n"
           << ar[2][0] << " " << ar[2][1] << " " << ar[2][2] << "\n";
    else
      cout << ans4 << "\n"
           << 4 << "\n"
           << ar[3][0] << " " << ar[3][1] << " " << ar[3][2] << " " << ar[3][3]
           << "\n";
  }
}
void ff() { ar[0][0] = l; }
void ss() {
  long long min_ = 1e16;
  for (long long i = l; i < r; i++) {
    if (min_ > (i ^ (i + 1))) {
      ar[1][0] = i, ar[1][1] = i + 1;
      min_ = (i ^ (i + 1));
      if (min_ == 1) break;
    }
  }
}
void tt() {
  ar[2][0] = l, ar[2][1] = l + 1, ar[2][2] = l + 2;
  long long bit = 0;
  for (int i = 60; i >= 0; i--) {
    if (l & (1ll << i)) {
      bit = i;
      break;
    }
  }
  long long x = l;
  long long y = l + (1ll << (bit + 1));
  long long z = (1ll << (bit + 1));
  y = (y ^ (1ll << (bit)));
  z = (z ^ (1ll << (bit)));
  if (y <= r && z <= r) ar[2][0] = x, ar[2][1] = y, ar[2][2] = z;
}
void fo() {
  ar[3][0] = l, ar[3][1] = l + 1, ar[3][2] = l + 2, ar[3][3] = l + 3;
  for (long long i = l; i < r - 2; i++) {
    if ((i & 3) == 0 || (i & 3) == 2) {
      ar[3][0] = i, ar[3][1] = i + 1, ar[3][2] = i + 2, ar[3][3] = i + 3;
      break;
    }
  }
}