#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string.h>

int check(char *st){
    int n = strlen(st);
//    std::cout<<n;
    for (int i = 0; i<=n/2; i++){
        if (st[i] != st[n-1-i]){
            return 0;
        }
    }
    return 1;
}

char * words[8] = {"kniga", "na", "upala", "lapu", "a", "stol", "roza", "azora"};

void swap( int a[], int i, int j ) // swap elements a[i], a[j]
{
    int temp = a[i] ;
    a[i] = a[j] ;
    a[j] = temp ;
}

void print_array( const int a[], int n )
{
    static int cnt = 0 ;
    char *res = (char*)calloc(128, sizeof(char));
    int * resint=(int*)calloc(100, sizeof(int));
    for( int i = 0 ; i < n ; ++i ) {
        strcat(res,words[a[i]]);
//        std::cout << res<< ' ';
    }
//    for( int i = 0 ; i < n ; ++i ) std::cout<<a[i]<<' ';
    if (check(res)) {
        for (int i = 0; i < n; i++) std::cout<<a[i]<<' ';
        std::cout<<std::endl;
        std::cout << std::setw(3) << ++cnt << ". " ;
        std::cout << res;
        std::cout << '\n';
    }
}

// array 'a' of size 'n', permute range starting at position 'from'
void permute( int a[], int n, int from = 0 )
{
    // if the entire range has been permuted, print the permutation
    if( from == n ) return print_array( a, n ) ;

    // else
    for( int i = from ; i < n ; ++i ) // repeat: for each element in the range to permute
    {
        swap( a, from, i ) ; // make this element the head (at position from)
        permute( a, n, from+1 ) ; // form all permutations of the tail (starting at from+1)
        swap( a, from, i ) ; // restore the original positions
    }
}


void comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's

    // print integers and permute bitmask
    do {
        int res[K];
        int q = 0;
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]){
                res[q] = i;
                q += 1;
            }
            //std::cout << " " << i;
        }
        q = 0;
        permute(res,K);
//        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}

int main(){
//    vector <string> words = {'книга', 'на', 'упала', 'лапу', 'а', 'стол', 'роза', 'азора'};
//    vector <string> res;

//    int n = words.size();
    for (int i = 1; i<= 8; i++) comb(8,i);
    return 0;
}