Description

求对于每一段子串，其前缀在母串上的最大匹配长度是多少呢？

Format

Input

第一行有两个整数，N和M，分别表示母串的长度和子串的个数。 第二行是一个长度为N的母串，所有字符都是E,S,W和N中的一个。 之后M行，每行有一个子串，所有字符都满是E,S,W和N中的一个。 N<=10^7，M<=10^5，每一段文字的长度<=100。

Output

输出有M行，对应M段文字。每一行输出一个数，表示这一个子串的前缀与母串的最大匹配串长度。。

Samples

7 3
SNNSSNS
NNSS
NNN
WSEE

4
2
0