// ads1.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct _string
{
    int length;
    char value[100010];
}string;

typedef struct _vertex
{
    int length;
    struct _vertex *back, *shortcut, *children[63];
    char value;
    int is_end : 2;
}vertex;

vertex *tree;

string *read_line(FILE *f)
{
    string *s = (string*)malloc(sizeof(string));
    if(fgets(s->value, 100005, f) == NULL) return NULL;
    s->length = strlen(s->value)-1;

    printf("%c %d\n", s->value[s->length - 1], s->length);
    //int momo; scanf("%d", &momo);
    return s;
}

void add_word(string *s)
{
    int i;
    vertex *tmp = tree;

    for(i = 0; i < s->length; ++i)
    {
        if(s->value[i] < 1) return;
        //printf("<%d>\n", s->value[i]);
        int index = 0;
        if(isdigit(s->value[i]))
        {
            index = s->value[i] - 48;
        }
        if(isupper(s->value[i]))
        {
            index = s->value[i] - 65 + 10;
        }
        if(islower(s->value[i]))
        {
            index = s->value[i] - 97 + 10 + 26;
        }

        if(tmp->children[index] == NULL)
        {
            tmp->children[index] = (vertex*)malloc(sizeof(vertex));
            int i;
            for(i = 0; i < 63; i++) tmp->children[index]->children[i] = NULL;
            tmp->children[index]->back = NULL;
            tmp->children[index]->shortcut = NULL;
            tmp->children[index]->value = s->value[i];
            tmp->children[index]->is_end = 0;
        }

        tmp = tmp->children[index];
    }

    tmp->is_end = 1;
    tmp->length = s->length;
}

int main(int argc, char** argv)
{
    tree = (vertex*)malloc(sizeof(vertex));
    tree->value = ' ';
    int i;
    for(i = 0; i < 63; i++)tree->children[i] = NULL;
    tree->back = NULL;
    tree->shortcut = NULL;
    tree->is_end = 0;
    tree->length = 0;


    string* text = read_line(stdin);
    while(1)
    {
        string *line = read_line(stdin);
        if(line == NULL) break;

        add_word(line);
    }

    //printf("add word se povedli\n");

    vertex *stack[100000];
    int stack_pointer = -1;
//  int i;
    for(i = 0; i < 63; ++i)
    {
        if(tree->children[i] != NULL)
        {
            if(tree->children[i]->value < 1)continue;
            tree->children[i]->back = tree;
            stack[++stack_pointer] = tree->children[i];

            //printf("pridal som do stacku, na poziciu %d tento prvok.value <%d>\n", stack_pointer, tree->children[i]->value);
        }
    }

    while(stack_pointer >= 0)
    {
            vertex *v = stack[stack_pointer--];
            //printf("vzal som zo stacku, z pozicie %d tento prvok.value <%d>\n", stack_pointer+1, v->value);
            int i;
            for(i = 0; i < 63; i++)
            {
                if(v->children[i] != NULL)
                {
                    stack[++stack_pointer] = v->children[i];

                    if(v->children[i]->value < 1)continue;
                    int index = 0;
                    //printf("<%d>\n", v->childre);
                    if(isdigit(v->children[i]->value))
                    {
                        index = v->children[i]->value - 48;
                    }
                    if(isupper(v->children[i]->value))
                    {
                        index = v->children[i]->value - 65 + 10;
                    }
                    if(islower(v->children[i]->value))
                    {
                        index = v->children[i]->value - 97 + 10 + 26;
                    }

                    vertex *n = v->back;
                    while(n != tree && n->children[index] == NULL) n = n->back;
                    if(n->children[index] != NULL) n = n->children[index];
                    v->children[i]->back = n;

                    if(v->children[i]->back->back != NULL && v->children[i]->back->back != tree) v->children[i]->back = v->children[i]->back->back;

                    if(v->children[i]->is_end == 1)
                    {
                        v->children[i]->shortcut = v->children[i]->back;
                        if(v->children[i]->back->shortcut != NULL) v->children[i]->shortcut = v->children[i]->back->shortcut;
                    }
                    else v->children[i]->shortcut = v->children[i]->shortcut;
                }

            }
    }


    vertex *a = tree;
    vertex *b = NULL;

    char znaky[100001];
    vertex *stavy[100001];
    int indexZnak = 0;
    int indexStav = 0;
    int k;
    for(k = 0; k < text->length; k++)
    {
        int index = 0;
        //printf("<%d>\n", v->childre);
        if(isdigit(text->value[k]))
        {
            index = text->value[k] - 48;
        }
        if(isupper(text->value[k]))
        {
            index = text->value[k] - 65 + 10;
        }
        if(islower(text->value[k]))
        {
            index = text->value[k] - 97 + 10 + 26;
        }

        vertex *n = a;
        while(n->children[index] == NULL && n != tree)
        {
            n = n->back;
        }
        if(n->children[index] != NULL) n = n->children[index];

        a = n;
        b = a;

        znaky[indexZnak] = text->value[k];
        indexZnak++;

        stavy[indexStav] = b;
        indexStav++;

        if(b->is_end == 1)
        {
            if(b->shortcut != NULL)
            {
                b = b->shortcut;
            }

            indexZnak -= b->length;
            indexStav -= b->length;
            //printf("odpocitavam %d\n", b->length);

            if(indexStav == 0) a = tree;
            else a = stavy[indexStav - 1];
        }
    }

    int momo;
    for(momo = 0; momo < indexZnak; momo++)
    {
        printf("%c", znaky[momo]);
    }
    printf("\n");
    ;
    //scanf("%d", &momo);


    return 0;
}