Mateusz and an Infinite Sequence
Contest: Hello 2019
Difficulty rating: 3400
Tags: bitmasks, brute force, dp, strings

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?

Input format:
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 < 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 < m$$$). The fifth line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq 10^{18}$$$, $$$r-l+1 \geq n$$$).

Output format:
Print a single integer — the answer to the problem.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
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$$$:

Example input:
2 2
0 1
4
0 1 1 0
2 21

Example output:
6

Example input:
3 4
0 1 2
2
0 2
6 11

Example output:
1

Editorial:
In the beginning, change the query about an interval into two queries about prefixes.
Nextly, let's generalize the problem. Change the condition $$$A_i \leq B_j$$$ into $$$A_i \in X_j$$$, where $$$X_j$$$ is some set of possible values (and will be represented as a bitmask).
The problem is that the length of the sequence from the input can be huge. How to decrease it? If we'd know the index of the position where we want to compare the sequence from the input taken modulo $$$d$$$, we'd be able to decrease the size of the sequence approximately $$$d$$$ times. How? We'd know the partition into groups of at most $$$d$$$ elements and one group can be reduced to one element (using binary shifts and AND operations).
We don't know the remainder as there can be many of them. The idea is to use the recursive function which will check every possibility. The function will take as an argument a sequence $$$X$$$ (the sequence of sets of possible elements for each position) and a length of the prefix. It will work as follows:
If the length of the sequence is equal to one, calculate the result with some DP which will be described later.
If the possible prefix is empty, return $$$0$$$.
In other cases, iterate over possible reminder and split into $$$d$$$ recursive calls, each with approximately $$$d$$$ times shorter sequence. How does this reduction work? If the sequence's length is big, the sum of lengths doesn't change much. The tricky part comes when the length of the sequence is $$$2$$$. Then, in $$$d-1$$$ calls, the length will change to one, but in one call the length will stay equal to two. This shouldn't scare us because these $$$d-1$$$ calls will be cut off instantly with mentioned DP.
In this way, we will generate $$$O(n \cdot log_d(r) \cdot d)$$$ queries. The next observation is that there will be only $$$O(log_d(r))$$$ different lengths of prefixes. To prove it we can consider how does the set of possible prefixes look like on each level of the recursion.
Now, for each mentioned prefix $$$a$$$ and each number $$$b$$$ from the range $$$[0, m)$$$ we should calculate how many times does $$$b$$$ appear on the prefix $$$a$$$. To do this, write $$$a$$$ in the $$$d$$$-based system and use simple DP which goes like $$$DP[i=number~of~already~considered~digits][j=remainder][l=are~we~aready~smaller~than~a]=number~of~ways$$$ with $$$0 \leq i \leq log_d(r)$$$, $$$0 \leq j < m$$$ and $$$0 \leq l \leq 1$$$.