Description

Original source: JSOI 2012

By the beautiful Xuanwu Lake, near Jiming Temple, and in front of Jilong Mountain, lies a fertile and picturesque land known as Jinxiang River. Legend has it that one day, a wisp of purple energy descended from the heavens and vanished into the Jinxiang River in an instant. The elders say this was the Xuanwu deity hiding celestial scriptures here.

Many years later, people finally discovered texts bearing the Xuanwu cipher in the Jinxiang River area. Even more mysteriously, these texts with the Xuanwu cipher subtly correlate with the structure of Taicheng on the southern shore of Xuanwu Lake. Thus began the long and arduous task of deciphering.

Through analysis, we can describe the arrangement of bricks in Taicheng using the four cardinal directions: east, south, west, and north. We can represent this with a sequence of length $N$, where each element is one of E, S, W, or N, corresponding to the four directions. This sequence is called the "mother string." The enigmatic Xuanwu cipher is described by patterns of the Four Symbols, which correspond to the four directions: the Azure Dragon of the East, the White Tiger of the West, the Vermilion Bird of the South, and the Black Tortoise (Xuanwu) of the North.

Now, archaeologists face a challenge. For each segment of the text, what is the maximum length of its prefix that matches a substring of the mother string?

Input Format

The first line contains two integers, $N$ and $M$, representing the length of the mother string and the number of text segments, respectively.
The second line is a string of length $N$, where each character is one of E, S, W, or N.
The following $M$ lines each contain a string representing a segment of the Xuanwu cipher text. Again, all characters are one of E, S, W, or N.

Output Format

Output $M$ lines, corresponding to the $M$ text segments.
Each line should contain a single number, representing the maximum length of the prefix of the text segment that matches a substring of the mother string.

Sample 1

7 3
SNNSSNS
NNSS
NNN
WSEE

4
2
0

Data Range and Hints

For all data, $1\le N\le 10^7$, $1\le M\le 10^5$, and the length of each text segment is guaranteed to be no more than 100.