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;
long long l, r, k;
long long a[1000010];
int d1;
struct node {
  long long w;
  long long b[5];
  int cnt;
};
node b[20];
long long c[5];
bool cmp(node a, node b) { return a.w < b.w; }
void dfs(long long l, long long r, int cent, long long v) {
  if (l > r) {
    if (!cent) return;
    b[d1].cnt = cent;
    for (int i = 0; i < cent; i++) b[d1].b[i] = c[i];
    b[d1++].w = v;
    return;
  }
  c[cent] = l;
  dfs(l + 1, r, cent + 1, v ^ l);
  dfs(l + 1, r, cent, v);
}
int main() {
  while (cin >> l >> r >> k) {
    long long ans, x;
    int d = 0, i, j;
    if (k == 1) {
      ans = l;
      a[d++] = l;
    } else {
      if (r - l < 4) {
        d1 = 0;
        dfs(l, r, 0, 0);
        sort(b, b + d1, cmp);
        for (i = 0; i < d1; i++)
          if (b[i].cnt <= k) {
            ans = b[i].w;
            for (j = 0; j < b[i].cnt; j++) a[d++] = b[i].b[j];
            break;
          }
      } else {
        if (k == 2) {
          for (x = l; x <= r; x++)
            if (x % 2 == 0) break;
          ans = 1;
          a[d++] = x;
          a[d++] = x + 1;
        } else if (k >= 4) {
          for (x = l; x <= r; x++)
            if (x % 2 == 0) break;
          ans = 0;
          a[d++] = x;
          a[d++] = x + 1;
          a[d++] = x + 2;
          a[d++] = x + 3;
        } else {
          long long now = l;
          int bi = 0;
          while (now) {
            now >>= 1;
            bi++;
          }
          now = 3;
          while (--bi) now <<= 1;
          if (now <= r) {
            ans = 0;
            a[d++] = now;
            a[d++] = now ^ l;
            a[d++] = l;
          } else {
            for (x = l; x <= r; x++)
              if (x % 2 == 0) break;
            ans = 1;
            a[d++] = x;
            a[d++] = x + 1;
          }
        }
      }
    }
    cout << ans << endl << d << endl;
    for (i = 0; i < d - 1; i++) cout << a[i] << ' ';
    cout << a[i] << endl;
  }
  return 0;
}