cipher

Time limit: 2s Memory limit: 256MB Input: Output:

The Vigenere Cipher is a well known cipher in cryptography. The encryption of a string ss, with the help of a key-string tt, both having the same lengths, is done by the following way:

Let ee be the final string that will be obtained by the encryption of string ss using the key tt.
The string ee will have the same length as the previous 22 strings, and will respect the following property:

ei=chr((ord(si)+ord(ti))mod  26)e_i=\textrm{chr} \biggl( \Bigl( \textrm{ord}(s_i)+\textrm{ord}(t_i) \Bigr) \mod 26 \biggr)

where ord(c)\textrm{ord}(c) is the ordinal number of the character cc in the english alphabet (ord(β€˜a’)=0\textrm{ord}(\texttt{`a'})=0, ord(β€˜z’)=25\textrm{ord}(\texttt{`z'})=25 and so on), and chr(i)\textrm{chr}(i) is the function that returns the character with the ordinal number ii in the english alphabet.

Briefly, the encryption process can be described as an iterative addition, character by character, modulo 26, of the string tt to the string ss.

Let's define a modification over the Vigenere Cipher, which we will refer to as: Cyclic Vigenere, the following way:

The encryption of string ss with key-string tt is possible only when the length of string tt divides the length of string ss. The result of the encryption is string ee, defined as:

ei=chr((ord(si)+ord(timodβ€‰β€‰βˆ£t∣))mod  26)e_i=\textrm{chr} \biggl( \Bigl( \textrm{ord}(s_i)+\textrm{ord}(t_{i \mod |t|}) \Bigr) \mod 26 \biggr)

where ∣t∣|t| denotes the length of the tt string, imodβ€‰β€‰βˆ£t∣i \mod |t| is the remainder of ii by ∣t∣|t|, and the indexing of the strings starts at 0.

Briefly, the encryption process can be described as an iterative addition, character by character, modulo 26, of the repetition of the string tt to the string ss.

In this task, KK key-strings are given, and NN strings that need to be encrypted. For any string sis_{i} from the NN strings, print the index of the key-string tjt_{j} that generates the minimal possible lexicographic encryption ee of the string sis_{i}. If there are multiple answers, the one with the smallest index must be printed. If there is no answer, print βˆ’1-1.

Input data

The first line of input contains NN and KK.

The next KK lines contain the key-strings t0,t1,…,tKβˆ’1t_0, t_1, \ldots, t_{K-1}.

The next NN lines contain the strings s0,s1,…,sNβˆ’1s_0, s_1, \ldots, s_{N-1}.

Output data

Output NN lines. The ii-th of them must contain the index of the key-string tjt_{j} that generates the minimal possible lexicographic encryption ee of the string sis_{i}. The indexes are considered to start from 11.

If there are multiple answers for any of the strings, print the minimal possible index of a key-string tjt_{j}.

If there is no such key-string, print βˆ’1-1.

Constraints and Clarifications

  • 1≀N≀2β‹…1051 \le N \le 2 \cdot 10^5.
  • 1≀K≀2β‹…1051 \le K \le 2 \cdot 10^5.
  • The total lengths of all strings and key-strings is at most 4β‹…1054 \cdot 10^5.
  • Each string contains only lowercase English letters.
# Score Restrictions
1 0 Examples.
2 20 The total length of all strings and key-strings multiplied by KK is at most 10610^6.
3 50 The length of each key-string divides the length of each string.
4 30 No additional limitations.

Example

stdin

3 6
are
mere
ana
oare
cinestie
nimeni
anaana
plebi
nusestie

stdout

3
-1
4

Explanation

In the sample, for the first string anaana, the key-string are produces aeeaee, the key-string ana produces aaaaaa, and the key-string nimeni produces nvmeai, the lexicographically minimal encryption result is aaaaaa, which is produced by the third key-string, so the answer is 33.

For the second string plebi, there is no suitable key-string, since it has length 5, which is not divisible by any of the lengths of the key-strings, thus the answer is βˆ’1-1.

For the third string nusestie, the key-string mere produces zyjiexzi, the key-string oare, produces bujigtzi, and the key-string cinestie produces pcfikmqi, the lexicographically minimal encryption result is bujigtzi, which is produced by the fourth key-string, so the answer is 44.

Log in or sign up to be able to send submissions!