CF1097H.Mateusz and an Infinite Sequence

A Thue-Morse-Radecki-Mateusz sequence (Thorse-Radewoosh sequence in short) is an infinite sequence constructed from a finite sequence $\mathrm{gen}$ of length $d$ and an integer $m$, obtained in the following sequence of steps:

• In the beginning, we define the one-element sequence $M_0=(0)$.
• In the $k$-th step, $k \geq 1$, we define the sequence $M_k$ to be the concatenation of the $d$ copies of $M_{k-1}$. However, each of them is altered slightly — in the $i$-th of them ($1 \leq i \leq d$), each element $x$ is changed to $(x+\mathrm{gen}_i) \pmod{m}$.

For instance, if we pick $\mathrm{gen} = (0, \color{blue}{1}, \color{green}{2})$ and $m = 4$:

• $M_0 = (0)$,
• $M_1 = (0, \color{blue}{1}, \color{green}{2})$,
• $M_2 = (0, 1, 2, \color{blue}{1, 2, 3}, \color{green}{2, 3, 0})$,
• $M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{blue}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{green}{2, 3, 0, 3, 0, 1, 0, 1, 2})$, and so on.

As you can see, as long as the first element of $\mathrm{gen}$ is $0$, each consecutive step produces a sequence whose prefix is the sequence generated in the previous step. Therefore, we can define the infinite Thorse-Radewoosh sequence $M_\infty$ as the sequence obtained by applying the step above indefinitely. For the parameters above, $M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots)$.

Mateusz picked a sequence $\mathrm{gen}$ and an integer $m$, and used them to obtain a Thorse-Radewoosh sequence $M_\infty$. He then picked two integers $l$, $r$, and wrote down a subsequence of this sequence $A := ((M_\infty)_l, (M_\infty)_{l+1}, \dots, (M_\infty)_r)$.

Note that we use the $1$-based indexing both for $M_\infty$ and $A$.

Mateusz has his favorite sequence $B$ with length $n$, and would like to see how large it is compared to $A$. Let's say that $B$ majorizes sequence $X$ of length $n$ (let's denote it as $B \geq X$) if and only if for all $i \in {1, 2, \dots, n}$, we have $B_i \geq X_i$.

He now asks himself how many integers $x$ in the range $[1, |A| - n + 1]$ there are such that $B \geq (A_x, A_{x+1}, A_{x+2}, \dots, A_{x+n-1})$. As both sequences were huge, answering the question using only his pen and paper turned out to be too time-consuming. Can you help him automate his research?

托尔-摩尔斯-拉德茨基-马泰乌什序列（简称“托尔-拉德沃什序列”）是一种由长度为 $d$ 的有限序列 $\mathrm{gen}$ 和整数 $m$ 构造出的无限序列，其构造步骤如下：

• 初始时，定义单元素序列 $M_0 = (0)$；
• 在第 $k$ 步（$k \geq 1$），将序列 $M_k$ 定义为 $d$ 个 $M_{k-1}$ 的拼接。但每个副本均作轻微修改：在第 $i$ 个副本中（$1 \leq i \leq d$），其中每个元素 $x$ 均被替换为 $(x + \mathrm{gen}_i) \bmod m$。

例如，若取 $\mathrm{gen} = (0, \color{blue}{1}, \color{green}{2})$ 且 $m = 4$，则有：

• $M_0 = (0)$，
• $M_1 = (0, \color{blue}{1}, \color{green}{2})$，
• $M_2 = (0, 1, 2, \color{blue}{1, 2, 3}, \color{green}{2, 3, 0})$，
• $M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{blue}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{green}{2, 3, 0, 3, 0, 1, 0, 1, 2})$，依此类推。

如你所见，只要 $\mathrm{gen}$ 的首元素为 $0$，则每一步生成的新序列都以此前一步生成的序列为前缀。因此，我们可以将无限托尔-拉德沃什序列 $M_\infty$ 定义为上述过程无限进行后所得的序列。对上述参数，有
$M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots)$。

马泰乌什选取了一个序列 $\mathrm{gen}$ 和一个整数 $m$，并据此生成了托尔-拉德沃什序列 $M_\infty$。随后他选取两个整数 $l$、$r$，并写下该序列的一个子序列
$A := \big((M_\infty)_l,\ (M_\infty)_{l+1},\ \dots,\ (M_\infty)_r\big)$。

注意：此处 $M_\infty$ 和 $A$ 均采用从 1 开始的下标。

马泰乌什有一个他钟爱的长度为 $n$ 的序列 $B$，他希望比较 $B$ 与 $A$ 的大小关系。我们称：当且仅当对所有 $i \in \{1, 2, \dots, n\}$ 均有 $B_i \geq X_i$ 时，序列 $B$ 控制（majorizes） 长度为 $n$ 的序列 $X$（记作 $B \geq X$）。

现在他想知道自己有多少个整数 $x$ 满足 $x \in [1,\ |A| - n + 1]$，使得
$B \geq (A_x,\ A_{x+1},\ A_{x+2},\ \dots,\ A_{x+n-1})$。
由于两个序列规模极大，仅靠纸笔计算这一问题耗时过长。你能帮他将这项研究自动化吗？

The first line contains two integers $d$ and $m$ ($2 \leq d \leq 20$, $2 \leq m \leq 60$) — the length of the sequence $\mathrm{gen}$ and an integer used to perform the modular operations. The second line contains $d$ integers $\mathrm{gen}_i$ ($0 \leq \mathrm{gen}_i \lt m$). It's guaranteed that the first element of the sequence $\mathrm{gen}$ is equal to zero.

The third line contains one integer $n$ ($1 \leq n \leq 30000$) — the length of the sequence $B$. The fourth line contains $n$ integers $B_i$ ($0 \leq B_i \lt m$). The fifth line contains two integers $l$ and $r$ ($1 \leq l \leq r \leq 10^{18}$, $r-l+1 \geq n$).

第一行包含两个整数 $d$ 和 $m$（$2 \leq d \leq 20$，$2 \leq m \leq 60$）—— 分别表示序列 $\mathrm{gen}$ 的长度以及用于执行模运算的整数。
第二行包含 $d$ 个整数 $\mathrm{gen}_i$（$0 \leq \mathrm{gen}_i \lt m$）。保证序列 $\mathrm{gen}$ 的第一个元素为零。

第三行包含一个整数 $n$（$1 \leq n \leq 30000$）—— 表示序列 $B$ 的长度。
第四行包含 $n$ 个整数 $B_i$（$0 \leq B_i \lt m$）。
第五行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq 10^{18}$，且 $r-l+1 \geq n$）。

Print a single integer — the answer to the problem.

输出一个整数——该问题的答案。

Thorse-Radewoosh sequence in the first example is the standard Thue-Morse sequence, so the sequence $A$ is as follows: $11010011001011010010$. Here are the places where the sequence $B$ majorizes $A$:

第一个例子中的 Thorse-Radewoosh 序列即为标准的 Thue-Morse 序列，因此序列 $A$ 如下：$11010011001011010010$。以下是序列 $B$ 主导（majorizes）序列 $A$ 的位置：