/* 
 * Kernighan-Pike: Practice of Programming, 1998
 * Addison-Wesley
 */

/* 
 * Az STL elemei template-ek, tehát számos
 * headert kell betölteni:
 *
 * adatszerkezetenként külön-külön 
 * es az algoritmusokat egyben
 * 
 */

#include <string>       // std::string      
#include <iostream>     // standard input-output

#include <deque>        // sor  (lopop, loext, hipop, hiext)
#include <map>          // rendezőfa
#include <vector>       // sorozat (hiext és hipop)


using namespace std;


const int nwords = 15000; // max output méret, szavakban
//const int npref = 1;
const int npref = 3;      // fokszám: figyelembe vett előző állapotok   
char NONWORD[] = "\n";    // extremális elem

// ez a típus képes tárolni az állapotátmeneteket
typedef map< deque<string>, vector<string> > map_t;

// ez a változó tárolja a mi állapotátmeneteinket
map_t statetab;

// felépíti az állapotátmeneteket:
// egy adott prefix után milyen s szó következik
void add( deque<string>& prefix, const string& s)
{
    if ( prefix.size() == npref ) // warning: unsigned==signed
    {
        statetab[prefix].push_back(s);
        prefix.pop_front(); // kiveszi a legrégebbi állapotot
    }
    prefix.push_back(s);    // berakja az újat
}

// eof-ig felépíti a táblánkat
void build( deque<string>& prefix, istream& in)
{
    string buf;

    while ( in >> buf )
        add( prefix, buf);  // közben prefix jobbra lép 
}

// outputot generál
void generate(int nwords)
{
    deque<string> prefix;
    int i;
    int len = 0;

    for ( i = 0; i < npref; ++i)
        add( prefix, NONWORD);

    // TODO: véletlenszámgenerátort inicializálni
    for ( i = 0; i < nwords; ++i)
    {
        // kiválasztjuk a prefix-hez tartozó szavak sorozatát
        vector<string>& suf = statetab[prefix];
        // és véletlenszerűen választunk egy szót
        const string& w = suf[rand() % suf.size()];

        if ( w == NONWORD )
            break;  // végállapot: befejezzük a generálást

        // csak a sorok tördelése miatt
        if ( len + w.size() > 70 )
        {
            cout << endl;
            len = 0;
        }
        cout << w << " ";
        len += w.size()+1;

        // következő prefix előállítása
        prefix.pop_front();
        prefix.push_back(w);
    }
}
int main()
{
    deque<string> prefix;
    // kezdeti állapot
    for ( int i = 0; i < npref; ++i)
        add( prefix, NONWORD);

    build( prefix, cin);    // táblázat felépítése eof-ig
    add( prefix, NONWORD);  // végállapot beállítása
    generate(nwords);       // output: legfeljebb nwords szó

    return 0;
}