Description

After analysis, we can use the four directions east, south, west, and north to describe how the Taicheng bricks are arranged. Let a sequence $s$ of length $n$ describe it, where the elements are E, S, W, N, representing the four directions east, south, west, and north. We call this the main string.

The mysterious Xuanwu cipher is $m$ segments of text described by the patterns of the Four Symbols. The Four Symbols are the Azure Dragon of the east, the White Tiger of the west, the Vermilion Bird of the south, and the Xuanwu of the north, corresponding to the four directions east, south, west, and north.

Now the archaeologists have met a difficult problem. For each text segment $t$, find its longest prefix $p$ such that $p$ is a substring of $s$.

Input Format

The first line contains two integers, representing the length $n$ of the main string and the number $m$ of text segments.

The second line contains a string of length $n$, representing the main string $s$.

The next $m$ lines each contain a string, representing a text segment $t$ with the Xuanwu cipher.

Output Format

For each text segment, output one integer per line, representing the length of the longest $p$.

7 3
SNNSSNS
NNSS
NNN
WSEE

4
2
0

Hint

Constraints

• For $20\%$ of the data, $n \leq 100$, $m \leq 50$.
• For $40\%$ of the data, $n \leq 2 \times 10^4$, $m \leq 2 \times 10^3$.
• For $70\%$ of the data, $n \leq 10^6$, $m \leq 2 \times 10^4$.
• For $100\%$ of the data, $1 \leq n \leq 10^7$, $1 \leq m \leq 10^5$, $1 \leq |t| \leq 100$, and both $s$ and $t$ contain only the letters E S W N.

Translated by ChatGPT 5