10391.cpp

//BISMILLAHIRRAHMANIRRAHIM
/*
 manus tar shopner soman boro
 all my suceesses are dedicated to my parents
 Author :: Shakil Ahmed
.............AUST_CSE27.........
 prob   ::
 Type   ::
 verdict::
 */

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pi acos(-1.0)
#define ff first
#define ss second
#define re return
#define QI queue<int>
#define SI stack<int>
#define SZ(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x) * (x))
#define ms(a,b) memset((a),(b),sizeof(a))
#define G() getchar()
#define MAX3(a,b,c) max(a,max(b,c))
#define II ( { int a ; read(a) ; a; } )
#define LL ( { Long a ; read(a) ; a; } )
#define DD ({double a; scanf("%lf", &a); a;})

double const EPS=3e-8;
using namespace std;

#define FI freopen ("input.txt", "r", stdin)
#define FO freopen ("output.txt", "w", stdout)

typedef long long Long;
typedef long long int64;
typedef unsigned long long ull;
typedef vector<int> vi ;
typedef set<int> si;
typedef vector<Long>vl;
typedef pair<int,int>pii;
typedef pair<string,int>psi;
typedef pair<Long,Long>pll;
typedef pair<double,double>pdd;
typedef vector<pii> vpii;

// For loop

#define forab(i, a, b)	for (__typeof (b) i = (a) ; i <= b ; ++i)
#define rep(i, n)		forab (i, 0, (n) - 1)
#define For(i, n)		forab (i, 1, n)
#define rofba(i, a, b)	for (__typeof (b)i = (b) ; i >= a ; --i)
#define per(i, n)		rofba (i, 0, (n) - 1)
#define rof(i, n)		rofba (i, 1, n)
#define forstl(i, s)	for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }

//Fast Reader
template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction

/* **************************************  My code start here ****************************************** */

vector < string > has[26];
int lim ;
bool cmp( string a , string b )
{
    if( a.size() == b.size() ) return a < b ;
    return a.size() < b.size() ;
}
bool ok( int sf , int i , int ef , int j ,  int s )
{
    int sza = has[sf][i].size();
    int szb = has[ef][j].size();
    int x = s , y = 0 ;
    while( x < sza && y < szb )
    {
        if( has[sf][i][x] != has[ef][j][y] ) return 0 ;
        x++;
        y++;
    }
  //  printf("yes");
    if( s && ( x != sza  || y != szb ) ) return 0 ;
    return 1 ;
}
int main()
{
   // I will always use scanf and printf
   // May be i won't be a good programmer but i will be a good human being
   string inp ;
   while( cin >> inp )
   {
       //if( inp == "#" ) break ;
       has[inp[0] - 'a'].pb( inp );
   }
   rep( i , 26 ) sort( has[i].begin() , has[i].end() , cmp );
   vector < string > ans ;
   int i , j , k , l ;
 //  printf(" After input ");
   for ( i = 0 ; i < 26 ; i++ )
   {
       int szs = has[i].size();
       if( szs == 0 ) continue ;
       for ( j = 1 ; j < szs ; j++ )
       {
          // if( j == 1 ) cout << has[i][0] << endl ;
          // cout << has[i][j] << endl ;
           bool found = 0 ;
           lim = has[i][j].size();
           for ( k = 0 ; k < j ; k++ )
           {
               if( ok( i , j , i ,  k , 0 ) )
               {
                   int s = has[i][k].size();
                   int st = has[i][j][s] - 'a';
                //   cout << " st " << st << endl ;
                   int szb = has[st].size();
                   for ( l = 0 ; l < szb ; l++ )
                   {
                        if( has[st][l].size() + s > lim ) break ;
                       if( ok( i , j , st , l , s ) )
                       {
                           found = 1 ;
                           ans.pb( has[i][j] );
                       }
                   }


               }
               if( found ) break ;
           }
       }
   }
   sort( ans.begin() , ans.end() );
   int sz = ans.size();
   rep( i , sz )
   {
       cout << ans[i] << endl ;
   }
    return 0;
}
/*
a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra
#
*/