cho.sh

Where To Go?

A note string uses upper case letters and each station name uses lower case letters, so a match between them is an equality-pattern match between two windows of different alphabets.

Medium6StringString matchingBrute forceHash mapNo attempts yetTime limit2sMemory limit512 MB

Problem

"RioCard only works in Rio??" (Dudu, 2014)

Dudu does not know any Thai, so before travelling from his hometown of Rio de Janeiro, Brazil to Bangkok, Thailand he wrote some useful sentences on a sheet of paper.

Most of them were ordinary small talk: "sa-wat-dee" (Hello), "pom cheu Dudu" (My name is Dudu), and "hoh wer-kraaf kong pom dtem-bpai-duay bplaa lai" (My hovercraft is full of eels).

He also prepared one sentence written in Thai: "Help me, I am a tourist and I don't speak Thai. Please let me know what train I should take to go to the Lumphini subway station."

When he arrived he was surprised twice over. His RioCard was useless, and the writing was not in Latin characters, so even "Hello" came out as สวัสดี.

At one point he got lost and wanted to go back to the hotel. He pulled out his big "help me" note and thought: "somewhere in this note there is the name of my station. Maybe I can figure out how to write it in Thai using the list of all stations."

The note is given as a string ss of upper case letters, and each station name is given as a string of lower case letters. Both spellings stand in for Thai characters, but they use different rules, so a letter of a station name cannot be compared with a letter of ss directly. Only the shape can be compared.

A station name of length mm can appear at position jj of ss when the letters of the name can be matched one to one with the letters of the substring sjsj+1…sj+m−1s_j s_{j+1} \dots s_{j+m-1} so that equal letters of the name sit over equal letters of ss, and different letters of the name sit over different letters of ss.

For example, if a station name is abla, then in Thai it is a four character word whose first and fourth characters are the same, and whose second and third characters differ from each other and from the first. Help Dudu find his station.

Input

The first line contains an integer NN, the number of stations in the subway system.

The second line contains the string ss with the sentence Dudu had prepared.

The following NN lines contain the names of the stations, one per line.

  • 1≤N≤10001 \le N \le 1000
  • 1≤∣s∣≤10001 \le |s| \le 1000

No station name is empty, and the sum of the lengths of all station names is at most 1000.

ss consists entirely of upper case letters. All station names consist entirely of lower case Latin letters, which represent Thai characters.

Output

Output NN lines, one for each station name.

On the ii-th line, output - if that station name cannot be in ss. Otherwise output a single number, the first position in ss where the station name could appear.

Hint

The first letter of ss is at position 0.

A station name longer than ∣s∣|s| can never appear.

A name made of a single letter always matches at position 0. A name with the same letter twice in a row matches only if ss also has the same letter twice in a row. A name made of kk different letters matches only if ss has a window of length kk made of kk different letters.