#include "stdio.h"
#include "string.h"
int book[100000],n,m,k[100000],cot=0;
char str[10000][10000],a[10000][10000],o[10000][10000];
void dfs(int step)
{
int c=0;
if(step==n)
{
cot++;
for(int i=0;i<n;i++)
{
printf("%s ",a[i]);
}
printf("\n");
return;
}
for(int i=0;i<n;i++)
{
if(book[i]==0)
{
for(int v=0;v<m;v++)
{
if(strstr(str[i],o[v])!=NULL&&step+1==k[v])
{
c++;
}
}
if(c==1)
{
c=0;
continue;
}
strcpy(a[step],str[i]);
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
}
int main()
{
scanf("%d %d",&n,&m);
getchar();
for (int i = 0; i < n; i++) {
scanf("%s", str[i]);
}
for (int i = 0; i < m; i++) {
scanf("%s %d", o[i],&k[i]);
}
dfs(0);
printf("%d",cot);
}