RT，TLE * 1，WA * 1

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
using namespace std;

int n,m,num,Map[26],ans[100002],fail[10000002],trie[10000002][4];
bool mark[10000002];
string S,str[100002];

void addstr(string s) {
	int tmp=0,len=s.size();
	for(int i=0;i<len;i++) {
		int to=Map[s[i]-'A'];
		if(!trie[tmp][to]) trie[tmp][to]=++num;
		tmp=trie[tmp][to];
	}
}

queue<int> q;

void getfail() {
	for(int i=0;i<4;i++) {
		int tmp=trie[0][i];
		if(tmp) q.push(tmp);
	}
	while(q.size()) {
		int tmp=q.front();
		q.pop();
		for(int i=0;i<4;i++) {
			if(trie[tmp][i]) {
				fail[trie[tmp][i]]=trie[fail[tmp]][i];
				q.push(trie[tmp][i]);
			} else trie[tmp][i]=trie[fail[tmp]][i];
		}
	}
}

void sum_up(string s) {
	int tmp=0,len=s.size();
	for(int i=0;i<len;i++) {
		tmp=trie[tmp][Map[s[i]-'A']];
		mark[tmp]=1;
		for(int j=tmp;j;j=fail[j]) mark[j]=1;
	}
}

void solve(string s,int pos) {
	int tmp=0,len=s.size();
	for(int i=0;i<len;i++) {
		int to=Map[s[i]-'A'];
		tmp=trie[tmp][to];
		if(mark[tmp]) ans[pos]=max(ans[pos],i+1);
	}
}

int main() {
	scanf("%d%d",&n,&m);
	Map['E'-'A']=0;
	Map['S'-'A']=1;
	Map['W'-'A']=2;
	Map['N'-'A']=3;
	cin>>S;
	for(int i=1;i<=m;i++) {
		cin>>str[i];
		addstr(str[i]);
	}
	getfail();
	sum_up(S);
	for(int i=1;i<=m;i++) {
		solve(str[i],i);
		printf("%d\n",ans[i]);
	}
	return 0;
}