Background

By the beautiful Xuanwu Lake, beside Jiming Temple and in front of Jilong Mountain, there is a rich and beautiful land called Jinxiang River. It is said that one day, a trace of purple aura came down from the sky, and in an instant it disappeared into the Jinxiang River. The elders said that this was the Xuanwu spirit hiding the heavenly book here.

Many years later, people finally found writings with the Xuanwu cipher in the Jinxiang River area. Even more amazingly, these writings with the Xuanwu cipher have a subtle connection with the structure of Taicheng on the south bank of Xuanwu Lake. Thus, the long work of deciphering began.

Problem 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