AT_jsc2019_final_e.Nearest String

高桥君可以对字符串 $a$ 进行以下两种操作：

• 删除 $a$ 的首位或末尾的 $1$ 个字符。该操作的花费为 $X$。
• 在 $a$ 的末尾添加任意 $1$ 个字符。该操作的花费为 $Y$。

现在高桥君有 $N$ 个字符串 $S_0,S_1,\cdots,S_{N-1}$。高桥君的朋友青木君会向他提出 $Q$ 个问题。

• 第 $i$ 个问题（$0 \leq i \leq Q-1$）：青木君给出字符串 $T_i$。请你计算，将 $T_i$ 通过上述操作反复变换，使其与高桥君拥有的 $N$ 个字符串中的某一个完全相同，所需的最小花费。

请你代替忙碌的高桥君，编写程序回答这些问题。

输入通过标准输入给出，格式如下：

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

输出 $Q$ 行。第 $i+1$ 行（$0 \leq i \leq Q-1$）输出第 $i$ 个问题的答案。

约束条件

• $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$）
• 所有输入的数均为整数。
• 所有输入的字符串均为小写英文字母组成。

样例说明 1

例如，考虑第 $2$ 个问题，可以按如下方式操作最优：

• 删除 abc 的首字母，得到 bc，花费 $4$。
• 在 bc 的末尾添加 d，得到 bcd，花费 $2$。

由 ChatGPT 4.1 翻译