#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
int zas[3000000];
char vzor[5000];
char text[3000000];
char vystup[3000000];
char vystup_R[3000000];
int main()
{
int n;
while ( scanf("%i %s", &n, vzor) == 2)
{
int vlen = strlen(vzor);
for(int l = 0; l < n; l++ )
{
int vystup_p = 0;
int vr = 0; // vrchol zas
int posl_vypsany = -1;
scanf("%s", text);
int p = 0;
int pvz = 0;
while(text[p] != '\0')
{
//printf("%c\n",text[p]);
if (text[p] == vzor[pvz]) // vzor pasuje
{
pvz++;
if (pvz == vlen)
{
if (vr == 0)
{
pvz = 0;
posl_vypsany = p;
}
else
{
pvz= zas[vr-1];
vr --;
}
}
}
else
{
if (pvz > 0 )
{
if (text[p] == vzor[0])
{
zas[vr] = pvz;
vr++;
pvz = 0;
p--;
}
else
{
int pvr = 0;
vystup_R[pvr++] = text[p];
for (int j = pvz -1; j >=0; j--)
vystup_R[pvr++] = vzor[j];
while(vr >= 0)
{
int h = zas[vr-1];
vr --;
for (int j = h -1; j >=0; j--)
vystup_R[pvr++] = vzor[j];
}
for (int m = pvr - 1; m >= 0; m--)
vystup[vystup_p++] = vystup_R[m];
posl_vypsany = p;
vr = 0;
pvz = 0;
}
}
else
{
for (int v = posl_vypsany+1; v <= p; v++){
vystup[vystup_p++] = text[v];
}
posl_vypsany = p;
// nesouvisi se vzorem
}
}
p++;
}
int pvr = 0;
for (int j = pvz -1; j >=0; j--)
vystup_R[pvr++] = vzor[j];
while(vr >= 0)
{
int h = zas[vr-1];
vr --;
for (int j = h -1; j >=0; j--)
vystup_R[pvr++] = vzor[j];
}
for (int m = pvr - 1; m >= 0; m--)
vystup[vystup_p++] = vystup_R[m];
vystup[vystup_p] = '\0';
printf("%s",vystup);
}
}
}