题目描述

在美丽的玄武湖畔、鸡鸣寺边、鸡笼山前，有一块富饶而秀美的土地，名为进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。

很多年后，人们终于在进香河地区发现了带有玄武密码的文字。经过分析，可以用东南西北四个方向来描述台城城砖的摆放，用一个长度为 $N$ 的序列来描述，序列中的元素分别是 E、S、W、N，代表东南西北四向，称之为母串。而神秘的玄武密码由四象的图案描述而成，共有 $M$ 段文字。这里的四象，分别是东之青龙、西之白虎、南之朱雀、北之玄武，与东南西北四向相对应。

现在，考古工作者遇到了一个难题：对于每一段文字，其前缀在母串上的最大匹配长度是多少？即对于每段文字，求出最长的前缀长度，使得该前缀是母串的一个子串。

输入格式

第一行有两个整数 $N$ 和 $M$，分别表示母串的长度和文字段的个数。

第二行是一个长度为 $N$ 的字符串，所有字符都是 E、S、W、N 之一。

接下来 $M$ 行，每行有一个字符串，描述一段带有玄武密码的文字。所有字符也都是 E、S、W、N 之一。

输出格式

输出共 $M$ 行，对应 $M$ 段文字。

每行输出一个整数，表示该段文字的前缀与母串的最大匹配串长度。

样例

7 3
SNNSSNS
NNSS
NNN
WSEE

4
2
0

样例解释
母串为 SNNSSNS。

• 文字 NNSS：最长能匹配的前缀是 NNSS，长度为 $4$；
• 文字 NNN：最长能匹配的前缀是 NN，长度为 $2$；
• 文字 WSEE：第一个字符 W 就没有匹配，因此长度为 $0$。

数据范围与提示

• $1 \le N \le 10^7$
• $1 \le M \le 10^5$
• 每一段文字的长度均不超过 $100$。