#include<iostream>
#include<string>
#include<queue>
using namespace std;
const int N=1e7+5,M=1e5+5;
int n,m;
int map[128];
int f[N][4],nxt[N],tot;
bool vis[N];
void inserted(const string &s){
	int len=s.size(),p=0;
	for(int i=0;i<len;i++){
		if(!f[p][map[s[i]]])
			f[p][map[s[i]]]=++tot;
		p=f[p][map[s[i]]];
	}
}
void built(){
	queue<int>q;
	for(int i=0;i<4;i++)
		if(f[0][i]) q.push(f[0][i]);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<4;i++){
			int v=f[u][i];
			if(v){
				nxt[v]=f[nxt[u]][i];
				q.push(v);
			}else f[u][i]=f[nxt[u]][i];
		}
	}
}
void check(const string &s){
	int len=s.size(),p=0;
	for(int i=0;i<len;i++){
		p=f[p][map[s[i]]];
		for(int j=p;j&&!vis[j];j=nxt[j])
			vis[j]=1;
	}
}
int found(const string &s){
	int len=s.size(),p=0,now=0;
	for(int i=0;i<len;i++){
		p=f[p][map[s[i]]];
		if(vis[p]) now=i+1;
	}
	return now;
}
string s[M];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	map['E']=0;map['S']=1;
	map['W']=2;map['N']=3;
	cin>>n>>m;
	cin>>s[0];
	for(int i=1;i<=m;i++){
		cin>>s[i];
		inserted(s[i]);
	}
	check(s[0]);
	for(int i=1;i<=m;i++)
		cout<<found(s[i])<<endl;
	return 0;
}