#include<stdio.h>
#include<malloc.h>
#include<string.h>
int NivelStiva[100];/*tine evidenta nivelului stivei la bktr*/
char string[100][50];/*primul sir de cuvinte*/
char AlDoileaSet[100][50];/*al doilea*/
 int n;
int k,m,lg,q;
int p;
FILE *f;
int FormezCuvinte(int p)
{

    int i,j;
    char a[50],b[50];
    /*creaza cuvinte formate din primele litere respectiv ultimile*/
    for (i=0;i<=p;i++)
    {
a[i]=string[NivelStiva[i]][0];
b[i]=string[NivelStiva[i]][lg-1];
    }
    a[i]='\0';
    b[i]='\0';
    /*cauta in al doilea set cuvintele formate*/
for (i=0;i<m;i++)
if (strcmp(AlDoileaSet[i],a)==0)
for (j=0;j<m;j++)
if (strcmp(AlDoileaSet[j],b)==0)
{
return 1;
}
return 0;
}
void Solutie(int p)
{
        int i;
/*daca solutia este valida o afiseaza*/
if (FormezCuvinte(p)==1)
{
    for (i=0;i<=p;i++)
    {
        printf("%s",string[NivelStiva[i]]);
    printf("\n");
    }
    printf("\n");
}
    return;
}
int valid (int p)
{
    /* daca gaseste 2 cuvinte identice consecutive trece cu forul  mai departe si nu adauga la solutia finala*/
    if (p>0 && strcmp(&string[NivelStiva[p]][0],&string[NivelStiva[p-1]][0])==0)
        return 0;
    else return 1;
}
/*bktr pentru generarea  solutiilor*/
void bktr(int p)
{
    int j;
    /*face combinari de n cuvinte luate cate k*/
    for (j=0;j<n;j++)
    {
        NivelStiva[p]=j;
        if (valid(p)==1)
            if (p==k-1)
                Solutie(p);
                else
                bktr(p+1);
    }
}

void main()
{
 int i;
    FILE  *f;
    /*citire din fisier*/
    f = fopen("ff.txt", "r");
    fscanf(f, "%d", &n);
    for (i = 0; i < n; i++)
        fscanf(f, "%s", &string[i]);
    fscanf(f, "%d", &m);
    for (i = 0; i < m; i++)
        fscanf(f, "%s", AlDoileaSet[i]);
    k = strlen(AlDoileaSet[0]);
    lg = strlen(string[0]);
bktr(0);
fclose(f);
    return;
}