Problem Description

For a string $ a $, Takahashi can perform the following two types of operations:

• Delete the first or last character of $ a $. This costs $ X $.
• Append any single character to the end of $ a $. This costs $ Y $.

Takahashi currently has $ N $ strings $S_0, S_1, \cdots, S_{N-1}$. His friend Aoki will ask him $ Q $ questions:

• Question $ i $ ($0 \leq i \leq Q-1$): Aoki shows a string $ T_i $. Repeat the above operations on $ T_i $ to make it match any of Takahashi's $ N $ strings, and find the minimum cost required to do so.

Create a program to answer these questions on behalf of the busy Takahashi.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ X $ $ Y $ $ S_0 $ $ S_1 $ $\vdots$ $ S_{N-1} $ $ T_0 $ $ T_1 $ $\vdots$ $ T_{Q-1} $

Output Format

Output $ Q $ lines. The $ i+1 $ ($0 \leq i \leq Q-1$) line should contain the answer to question $ i $.

Sample Input and Output

Sample Input #1

3 3 4 2
b
bcd
cd
a
ab
abc

Sample Output #1

6
4
6

Sample Input #2

4 3 1 100
a
aaaa
aaaaaaa
aaaaaaaaaa
aaa
aaaaaa
aaaaaaaaa

Sample Output #2

2
2
2

Sample Input #3

10 10 86 69
bbabbaaaaa
babaababab
bbababbbba
aaaaaaaaab
bbbbbbaabb
aabbabbbba
babbbbbbaa
baaabbaaaa
aaaaababbb
ababaaaaaa
bbaabbbbaa
abbbbabbbb
abbaaabaaa
ababaaaaab
bbaabbaaaa
abbbbbbabb
aabbbabbba
aaabbbaaaa
abbbababab
babaaabbbb

Sample Output #3

930
620
775
155
775
465
775
930
620
620

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq X, Y \leq 10^9$
• $1 \leq |S_i|$
• $\sum_{i=0}^{N-1} |S_i| \leq 5 \times 10^5$
• $S_i \neq S_j$ ($i \neq j$)
• $1 \leq |T_i|$
• $\sum_{i=0}^{Q-1} |T_i| \leq 5 \times 10^5$
• $T_i \neq T_j$ ($i \neq j$)
• All input numbers are integers.
• All input strings consist of lowercase English letters.

Sample Explanation 1

For example, considering question $ 2 $, the optimal operations are as follows:
- Delete the first character of abc to get bc. This costs $ 4 $.
- Append d to the end of bc to get bcd. This costs $ 2 $.

见题面 Input 部分

见题面 Output 部分