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 long long MAX = 1LL << 50;
void wypisz1(long long a) { cout << a << "\n1\n" << a << '\n'; }
void wypisz2(long long a, long long b) {
  cout << (a ^ b) << "\n2\n" << a << ' ' << b << '\n';
}
void wypisz3(long long a, long long b, long long c) {
  cout << (a ^ b ^ c) << "\n3\n" << a << ' ' << b << ' ' << c << '\n';
}
void wypisz4(long long a, long long b, long long c, long long d) {
  cout << (a ^ b ^ c ^ d) << "\n4\n"
       << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
bool zeruje_sie(long long a, long long b) {
  long long pot = 1;
  while (pot < MAX) {
    long long x = 3 * pot, z = 2 * pot - 1;
    if (a <= z && x <= b) {
      wypisz3(z, x - 1, x);
      return true;
    }
    pot *= 2;
  }
  return false;
}
bool bit(long long m, long long i) { return ((m >> i) & 1) == 1; }
void min_xor(long long a, long long b) {
  long long mini = a, maska = 1, maks = (1 << (b - a + 1)) - 1;
  for (long long m = (1); m <= (maks); m++) {
    long long w = 0;
    for (long long k = 0; k < (b - a + 1); k++)
      if (bit(m, k)) w ^= (a + k);
    if (w < mini) {
      mini = w;
      maska = m;
    }
  }
  int licz = 0;
  for (long long k = 0; k < (b - a + 1); k++)
    if (bit(maska, k)) licz++;
  cout << mini << '\n' << licz << '\n';
  for (long long k = 0; k < (b - a + 1); k++)
    if (bit(maska, k)) cout << a + k << ' ';
  cout << '\n';
}
void dwa(long long a) {
  if (a % 2 != 0) a++;
  wypisz2(a, a + 1);
}
void cztery(long long a) {
  if (a % 2 != 0) a++;
  wypisz4(a, a + 1, a + 2, a + 3);
}
void zrob_test(long long a, long long b, long long k) {
  if (k > 4) cztery(a);
  switch (k) {
    case 1:
      wypisz1(a);
      break;
    case 2: {
      if (b - a >= 2)
        dwa(a);
      else
        min_xor(a, b);
      break;
    }
    case 3: {
      if (!zeruje_sie(a, b)) dwa(a);
      break;
    }
    case 4: {
      if (b - a >= 4)
        cztery(a);
      else
        min_xor(a, b);
      break;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  long long a, b, k;
  cin >> a >> b >> k;
  zrob_test(a, b, k);
  return 0;
}