A93086.「雅礼集训 2018 Day11」字符串

有 $N$ 个字符串，每个字符串有一个权值 $v_i$。随后给出 $M$ 次询问，每次对一个区间进行检测。令最长的字符串长度为 $L$，那么会给出 $g_1, ..., g_L$ 表示每个长度的字符串的「识别值」。

对若干个字符串构成的集合 $P$ 进行测试的过程如下：

对字符串 $S$ 定义 $f(S)$ 表示 $S$ 在 $P$ 中以其为前缀出现的串的权值和。 那么如果 $S$ 在 $P$ 中作为前缀出现过，并且 $Bf(S) + A\times {\rm len}(S) \geq C$，那么则将 $g_{{\rm len}(S)}$ 加入集合 $G$。

最后随机选择一个区间 $[x, y](1 \leq x \leq y \leq L)$，如果 $[x, y] \bigcap G \neq \emptyset$，那么测试成功，否则测试失败。输出测试成功的概率并用最简分数表示。

特别地，整数 $k$ 表示为 $k / 1$。

第一行四个数 $N, A, B, C$。

接下来一行 $N$ 个数 $v_1, ..., v_N$。

接下来 $N$ 行表示 $N$ 个字符串。

接下来一行 $L$ 个数表示 $g_{1}, ... ,g_L$，保证 $g_1, ..., g_L$ 是一个 $1$ 至 $L$ 的排列。

接下来一行一个数 $M$。

接下来 $M$ 行，每行两个数 $l, r$，表示对第 $l$ 到第 $r$ 个字符串进行测试。

$M$ 个数表示答案。

测试点编号	$N, M \leq $	$\sum\left\vert s_i\right\vert \leq $	$s_i \leq $
1	$10$	$30$
2	$100$	$300$
3	$1000$	$3000$
4	$10000$	$30000$	$10$
5	$10^5$	$3\times 10^5$	$10$
6	$10000$	$30000$
7	$20000$	$50000$
8	$30000$	$70000$
9	$50000$	$100000$
10	$10^5$	$3\times 10^5$

对于 $100 \%$ 的数据， $0 \leq v_i, A, B, C \leq 10^9$。