Longest Prefix Substring Query

We are given a string s of length \( n \) composed solely of the characters E, S, W, N representing the four directions: East, South, West, and North respectively. This string describes the arrangement of bricks.

In addition, we have \( q \) query texts. For each query text t (of length \( m \)), your task is to find its longest prefix \( p \) such that \( p \) appears as a substring in s. A substring is a contiguous segment of a string.

For each query, output the desired prefix on a new line. If no non-empty prefix of t appears in s, output an empty string.

inputFormat

The input consists of multiple lines as follows:

• The first line contains the string s (length \( n \)).
• The second line contains an integer \( q \), the number of queries.
• Each of the next \( q \) lines contains a query string t.

outputFormat

For each query, output a single line containing the longest prefix of t that appears as a substring in s. If no non-empty prefix is found, output an empty line.

sample

ESWN
3
E
EW
WNE

E
E
WN