原題來自：JSOI 2012
在美麗的玄武湖畔，雞鳴寺邊，雞籠山前，有一塊富饒而秀美的土地，人們喚作進香河。相傳一日，一縷紫氣從天而至，只一瞬間便消失在了進香河中。老人們說，這是玄武神靈將天書藏匿在此。
很多年后，人們終于在進香河地區(qū)發(fā)現(xiàn)了帶有玄武密碼的文字。更加神奇的是，這份帶有玄武密碼的文字，與玄武湖南岸臺城的結(jié)構(gòu)有微妙的關(guān)聯(lián)。于是，漫長的破譯工作開始了。
經(jīng)過分析，我們可以用東南西北四個方向來描述臺城城磚的擺放，不妨用一個長度為 N 的序列來描述，序列中的元素分別是 E，S，W，N，代表了東南西北四向，我們稱之為母串。而神秘的玄武密碼是由四象的圖案描述而成的 M 段文字。這里的四象，分別是東之青龍，西之白虎，南之朱雀，北之玄武，對東南西北四向相對應(yīng)。
現(xiàn)在，考古工作者遇到了一個難題。對于每一段文字，其前綴在母串上的最大匹配長度是多少呢？
輸入
第一行有兩個整數(shù)，N 和 M，分別表示母串的長度和文字段的個數(shù)；
第二行是一個長度為 N 的字符串，所有字符都滿足是 E，S，W 和 N 中的一個；
之后 M 行，每行有一個字符串，描述了一段帶有玄武密碼的文字。依然滿足，所有字符都滿足是 E，S，W 和 N 中的一個。
輸出
輸出有 M 行，對應(yīng) M 段文字。
每一行輸出一個數(shù)，表示這一段文字的前綴與母串的最大匹配串長度。