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 int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int maxn = 70;
pair<long long, long long> dp[maxn][2][2][2][2][2][2];
string getstr(long long x) {
  string s;
  for (int i = 0; i < 60; ++i) {
    s += (char)('0' + x % 2);
    x /= 2;
  }
  reverse(s.begin(), s.end());
  return s;
}
int lval[maxn];
int rval[maxn];
void calcfl(int d, int u, int curb, int ind, int& rd, int& ru) {
  rd = d;
  if (curb > lval[ind]) rd = 1;
  ru = u;
  if (curb < rval[ind]) ru = 1;
  if (!d && curb < lval[ind]) rd = -1;
  if (!u && curb > rval[ind]) ru = -1;
}
int main() {
  long long l, r;
  int k;
  cin >> l >> r >> k;
  int cc = min(10LL, (r - l + 1));
  long long bestans = 1e18;
  vector<long long> bestset;
  for (int msk = 1; msk < (1 << cc); ++msk) {
    vector<long long> curset;
    for (int i = 0; i < cc; ++i)
      if (msk & (1 << i)) curset.push_back(l + i);
    long long curval = 0;
    if (int((curset).size()) > k) continue;
    for (int i = 0; i < int((curset).size()); ++i) curval ^= curset[i];
    if (curval < bestans) {
      bestans = curval;
      bestset = curset;
    }
  }
  string sl = getstr(l);
  for (int i = 0; i < 60; ++i) lval[i] = sl[i] == '1';
  string sr = getstr(r);
  for (int i = 0; i < 60; ++i) rval[i] = sr[i] == '1';
  memset(dp, -1, sizeof(dp));
  dp[0][0][0][0][0][0][0] = make_pair(0, 0);
  long long tl = 0;
  long long tr = 0;
  for (int i = 0; i < 60; ++i)
    for (int fd1 = 0; fd1 < 2; ++fd1)
      for (int fu1 = 0; fu1 < 2; ++fu1)
        for (int fd2 = 0; fd2 < 2; ++fd2)
          for (int fu2 = 0; fu2 < 2; ++fu2)
            for (int fd3 = 0; fd3 < 2; ++fd3)
              for (int fu3 = 0; fu3 < 2; ++fu3) {
                pair<long long, long long> cur =
                    dp[i][fd1][fu1][fd2][fu2][fd3][fu3];
                if (cur.first == -1) continue;
                for (int da = 0; da < 2; ++da)
                  for (int db = 0; db < 2; ++db) {
                    int dc = da ^ db;
                    long long ta = (cur.first << 1) | da;
                    long long tb = (cur.second << 1) | db;
                    long long tc = ta ^ tb;
                    int td1, td2, td3;
                    int tu1, tu2, tu3;
                    calcfl(fd1, fu1, da, i, td1, tu1);
                    calcfl(fd2, fu2, db, i, td2, tu2);
                    calcfl(fd3, fu3, dc, i, td3, tu3);
                    if (td1 == -1 || td2 == -1 || td3 == -1 || tu1 == -1 ||
                        tu2 == -1 || tu3 == -1)
                      continue;
                    dp[i + 1][td1][tu1][td2][tu2][td3][tu3] = make_pair(ta, tb);
                  }
              }
  for (int fd1 = 0; fd1 < 2; ++fd1)
    for (int fu1 = 0; fu1 < 2; ++fu1)
      for (int fd2 = 0; fd2 < 2; ++fd2)
        for (int fu2 = 0; fu2 < 2; ++fu2)
          for (int fd3 = 0; fd3 < 2; ++fd3)
            for (int fu3 = 0; fu3 < 2; ++fu3) {
              pair<long long, long long> cur =
                  dp[60][fd1][fu1][fd2][fu2][fd3][fu3];
              if (cur.first != -1) {
                long long curans = 0;
                vector<long long> curres;
                curres.push_back(cur.first);
                curres.push_back(cur.second);
                curres.push_back(cur.first ^ cur.second);
                if (k >= 3 && bestans > curans) {
                  bestans = curans;
                  bestset = curres;
                }
              }
            }
  cout << bestans << "\n";
  cout << int((bestset).size()) << "\n";
  for (int i = 0; i < int((bestset).size()); ++i) cout << bestset[i] << " ";
  return 0;
}