#include <cstdio>

 #include <vector>

 #include <algorithm>

 #define maxn 20010

 using namespace std;

 struct node {

     char v;

     int sz;

     bool isword, mark;

     node *son[], *pre;

 }pool[maxn], *tail=pool, *null=pool;

 char temp[];

 struct Trie {

     node *root;

     vector<node*> stk;

     node* newnode( node *p, char v ) {

         node *nd = ++tail;

         nd->sz = ;

         nd->v = v;

         nd->isword = nd->mark = false;

         nd->pre = p;

         for( int i=; i<; i++ ) nd->son[i] = null;

         return nd;

     }

     void insert( const char *str ) {

         if( !root ) root=newnode(null,'^');

         node *nd=root;

         while() {

             if( *str ) {

                 if( nd->son[*str-'a']==null ) nd->son[*str-'a']=newnode(nd,*str-'a');

                 nd->sz++;

                 nd = nd->son[*str-'a'];

                 str++;

             } else {

                 nd->isword = true;

                 stk.push_back( nd );

                 return;

             }

         }

     }

     void make_mark( node *nd ) {

         if( nd->isword ) {

             nd->mark = true;

             for( int i=; i<; i++ )

                 if( nd->son[i]!=null ) make_mark(nd->son[i]);

         } else if( nd->sz== ) {

             nd->mark = true;

         } else {

             for( int i=; i<; i++ )

                 if( nd->son[i]!=null ) make_mark(nd->son[i]);

         }

     }

     char *get( node *bt ) {

         while( !bt->mark ) bt=bt->pre;

         int i;

         for( i=; bt!=root; i++,bt=bt->pre )

             temp[i] = bt->v+'a';

         temp[i] = ;

         reverse( temp, temp+i );

         return temp;

     }

     void print( node *nd ) {

         fprintf( stderr, "nd %d ch %c mark %d\n", nd-pool, nd->v+'a', nd->mark );

         for( int i=; i<; i++ )

             if( nd->son[i]!=null ) print(nd->son[i]);

     }

 }T;

 void pt( char *st ) {

     fprintf( stderr, "%s\n", st );

 }

 char str[][];

 int main() {

     int i;

     for( i=; ; i++ ) {

         if( scanf( "%s", str[i] )!= ) {

             i--;

             break;

         }

         T.insert( str[i] );

     }

     for( int i=; i<; i++ )

         if( T.root->son[i]!=null )

             T.make_mark( T.root->son[i] );

     for( int t=; t<=i; t++ )

         printf( "%s %s\n", str[t], T.get(T.stk[t]) );

 }