Print all combinations which can be made by $k$ different elements from $0, 1, ..., n-1$. Note that we represent $0, 1, ... n-1$ as 00...0001, 00...0010, 00...0100, ..., 10...0000 in binary respectively and the integer representation of a combination is calculated by bitwise OR of the selected elements.

Constraints

* $1 \leq n \leq 18$
* $k \leq n$

Input

The input is given in the following format.


$n \; k$


Output

Print the combinations ordered by their decimal integers. Print a combination in the following format.


$d$: $e_0$ $e_1$ ...


Print ':' after the integer value $d$, then print elements $e_i$ in the combination in ascending order. Separate two adjacency elements by a space character.

Example

Input

5 3


Output

7: 0 1 2
11: 0 1 3
13: 0 2 3
14: 1 2 3
19: 0 1 4
21: 0 2 4
22: 1 2 4
25: 0 3 4
26: 1 3 4
28: 2 3 4
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

// #define DEBUG

vector<vector<int>> combination(int n, int k)
{
    vector<vector<int>> combination_for_return;
    if (k == 0)
        ;
    else if (k == 1)
    {
        for (int i = 0; i < n; i++)
        {
            vector<int> x = {i};
            combination_for_return.push_back(x);
        }
    }

    else
    {
        for (int i = k - 1; i < n; i++)
        {
            for (auto x : combination(i, k - 1))
            {
                x.push_back(i);
                combination_for_return.push_back(x);
            }
        }
    }
    return combination_for_return;
}

void enumerate_comnination(vector<int> x){
    ll s = 0;
    for (auto y : x)
        s += pow(2, y);
    cout << s << ":";
    for (auto y : x)
        cout << " " << y;
    cout << endl;
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, k, m;
    cin >> n >> k;
    m = 0;
    for (auto x : combination(n, k))
    {
        enumerate_comnination(x);
    }
    return 0;
}

