#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10, M=1e5+10;
int id, ch[N][4], pre[N], ys[150];
char str[N], t[M][105];
void ins(char *s)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int j=ys[s[i]];
        if(!ch[p][j]) ch[p][j]=++id;
        p=ch[p][j];
    }
}
bool v[N];
void AC()
{
    queue<int>q;for(int i=0;i<4;i++) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            int &y=ch[x][i];
            if(y==0)     y=ch[ pre[x] ][i];
            else    pre[y]=ch[ pre[x] ][i], q.push(y);
        }
    }
    int p=0;memset(v,0,sizeof(v));
    for(int i=0;str[i];i++)
    {
        p=ch[p][ys[str[i]]];
        for(int j=p;j && !v[j] ;j=pre[j])v[j]=1;
    }
}
int query(char *s)
{
    int p=0, ret=0;
    for(int i=0;s[i];i++)
    {
        p=ch[p][ys[s[i]]];
        if(v[p])ret=i+1;
    }
    return ret;
}
int main()
{
    ys['E']=0, ys['S']=1, ys['W']=2, ys['N']=3;
    int n, m;scanf("%d%d", &n, &m);
    scanf("%s", str);
    id=0;memset(ch,0,sizeof(ch));
    for(int i=1;i<=m;i++)scanf("%s", t[i]), ins(t[i]);
    memset(pre,0,sizeof(pre));AC();    
    for(int i=1;i<=m;i++)printf("%d\n", query(t[i]));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10,M=1e5+10;
int id,ch[N][4],pre[N],ys[150];
char str[N],t[M][105];
void ins(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int j=ys[s[i]];
		if(!ch[p][j]) ch[p][j]=++id;
		p=ch[p][j];
	}
}
bool v[N];
void AC()
{
	queue<int>q;for(int i=0;i<4;i++) if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<4;i++)
		{
			int &y=ch[x][i];
			if(y==0)     y=ch[ pre[x] ][i];
			else    pre[y]=ch[ pre[x] ][i],q.push(y);
		}
	}
	int p=0;memset(v,0,sizeof(v));
	for(int i=0;str[i];i++)
	{
		p=ch[p][ys[str[i]]];
		for(int j=p;j && !v[j] ;j=pre[j])v[j]=1;
	}
}
int query(char *s)
{
	int p=0,ret=0;
	for(int i=0;s[i];i++)
	{
		p=ch[p][ys[s[i]]];
		if(v[p])ret=i+1;
	}
	return ret;
}
int main()
{
	ys['E']=0,ys['S']=1,ys['W']=2,ys['N']=3;
	int n,m;scanf("%d%d",&n,&m);
	scanf("%s",str);
	id=0;memset(ch,0,sizeof(ch));
	for(int i=1;i<=m;i++)scanf("%s",t[i]),ins(t[i]);
	memset(pre,0,sizeof(pre));AC();	
	for(int i=1;i<=m;i++)printf("%d\n",query(t[i]));
	return 0;
}