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 翻译