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>
long long l, r, k, b[20], getans[20], tot, ans;
using namespace std;
int search(long long xx, long long p, long long a) {
  int j;
  if (p < k && a < ans) {
    for (j = 1; j <= k; j++) getans[j] = b[j];
    ans = a;
  }
  if (p == 0 || xx > r) return 1;
  search(xx + 1, p, a);
  tot++;
  b[tot] = xx;
  search(xx + 1, p - 1, a ^ xx);
  b[tot] = 0;
  tot--;
}
int main() {
  long long x, len, y, z, i;
  cin >> l >> r >> k;
  if ((r - l + 1) <= 5) {
    ans = l;
    tot = 0;
    for (i = 1; i <= k; i++) b[i] = 0;
    search(l, k, 0);
    tot = 0;
    for (i = 1; i <= k; i++)
      if (getans[i] > 0) tot++;
    if (tot > 0) {
      cout << ans << endl;
      cout << tot << endl;
      for (i = 1; i <= tot - 1; i++) cout << getans[i] << " ";
      cout << getans[tot];
    } else {
      cout << ans << endl;
      cout << "1" << endl;
      cout << l << endl;
    }
  } else {
    if (k == 1) {
      cout << l << endl << "1" << endl << l << endl;
    } else if (k == 2) {
      cout << "1" << endl << "2" << endl;
      if (l % 2 == 1) l++;
      cout << l << " " << l + 1 << endl;
    } else if (k >= 4) {
      cout << "0" << endl << "4" << endl;
      if (l % 2 == 1) l++;
      cout << l << " " << l + 1 << " " << l + 2 << " " << l + 3 << endl;
    } else {
      x = l;
      len = 0;
      while (x > 0) {
        len++;
        x = x / 2;
      }
      x = ((long long)1 << (len)) + ((long long)1 << (len - 1));
      if (x <= r) {
        cout << "0" << endl << "3" << endl;
        y = x - 1;
        z = ((long long)1 << len) - 1;
        cout << z << " " << y << " " << x << endl;
      } else {
        cout << "1" << endl << "2" << endl;
        if (l % 2 == 1) l++;
        cout << l << " " << l + 1 << endl;
      }
    }
  }
  i = 1;
}