#include<string>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e7+10;
const int M=1e5+10;
const int M2=1e2+10;
int trie[M*M2][4],tot,fail[N],vis[N];
int ans,n,m;
string str[M],p;
int idx(char p){
	if(p=='E') return 0;
	else if(p=='S') return 1;
	else if(p=='W') return 2;
	else return 3;
}
void insert(string s) {
	int pos=0,next,len=s.size();
	for(int i=0; i<len; i++) {
		next=idx(s[i]);
		if(!trie[pos][next]) trie[pos][next]=++tot;
		pos=trie[pos][next];
	}
	return ;
}
void bfs_fail() {
	queue<int>que;
	for(int i=0; i<4; i++) {
		if(trie[0][i])
			que.push(trie[0][i]),fail[trie[0][i]]=0;
	}
	while(!que.empty()) {
		int top=que.front();
		que.pop();
		for(int i=0; i<4; i++)
			if(trie[top][i]) {
				int pos=trie[top][i];
				que.push(pos);
				int u=fail[top];
				while(u&&!trie[u][i]) u=fail[u];
				fail[pos]=trie[u][i];
				
			} else trie[top][i]=trie[fail[top]][i];
	}
}
void query(string s) {
	int res=0,pos=0;
	for(int i=0; i<n; i++) {
		pos=trie[pos][idx(s[i])];
		vis[pos]=1;
		int u=pos;
		while(u&&!vis[u]) {
			vis[u]++;
			u=fail[u];
		}
	}
	return ;
}
inline int solve(string s) {
	int pos=0,ans=0;
	for(int i=0;i<s.size();i++){
		int next=idx(s[i]);
		pos=trie[pos][next];
		if(vis[pos]) ans=i+1;
	}
	return ans;
}
int main() {
    cin>>n>>m;
    cin>>p;
    for(int i=1;i<=m;i++) cin>>str[i],insert(str[i]);
    bfs_fail(),query(p);
    for(int i=1;i<=m;i++) printf("%d\n",solve(str[i]));
	return 0;
}

record