#include <iostream>
#include <string>

std::string gramatyka( std::string napis, int n )
{
    while(n--)
    {
        int i = napis.length() - 1;
        if( napis[ i ] == 'S' )
        {
            napis[i] = 'A';
            napis += "A";
        }
        else
        {
            napis[i] = 'S';
            napis += "S";
        }
    }
    return napis;
}

std::string zamien_gramatyka( std::string napis )
{
    for( unsigned int i = 0; i < napis.length(); i++ )
    {
        if( napis[i] == 'S' )
            napis[i] = '0';
        else
            napis[i] = '1';
    }

    return napis;
}

void wypisz_gramatyke()
{
    std::cout << "G = ( V, T, P, S )" << std::endl
              << "V = { S, A }" << std::endl
              << "T = { 0, 1 }" << std::endl
              << "P = { S -> AA|0, A -> SS|1 }" << std::endl
              << "S = { S }" << std::endl;
}

bool sprawdz_znak_poczatkowy( std::string napis )
{
    if( napis.length() != 1 || (napis[0] != 'A' && napis[0] != 'S'))
        return false;
    return true;
}

int main()
{
    std::string napis = "S";
    int n;

    //std::cout << "Podaj znak pocz¹tkowy: ";
    //std::cin >> napis;
    if( sprawdz_znak_poczatkowy( napis ) == false )
    {
        //std::cout << "Podano zly znak poczatkowy, uzywaj tylko A i S";
        return -1;
    }

    wypisz_gramatyke();

    std::cout << "Podaj liczbe n: ";
    std::cin >> n;

    for( int i = 1; i < n; i++)
    {
        std::cout << zamien_gramatyka( gramatyka( napis, i ) ) << std::endl;
    }

    return 0;
}