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?

Input

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

Print a single integer — the answer to the problem.Examplesinput

output

input

output

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

Solution:

#include <bits/stdc++.h>

using namespace std;

const int MAX = 30010;

struct State {
bitset<MAX> left;
bitset<MAX> right;
long long len = 0;
long long res = 0;
};

int n;
bitset<MAX> all;

State Unite(const State& a, const State& b) {
State c;
c.len = a.len + b.len;
c.res = a.res + b.res;
c.left = a.left;
c.right = b.right;
if (a.len < n - 1) {
    c.left &= (b.left >> a.len) | (all << (n - 1 - a.len));
  }
  if (b.len < n - 1) {
    c.right &= (a.right << b.len) | (all >> (n - 1 - b.len));
}
if (a.len + b.len >= n) {
bitset<MAX> d = a.right & b.left;
if (a.len < n - 1) {
      d &= (all >> (n - 1 - a.len));
}
if (b.len < n - 1) {
      d &= (all << (n - 1 - b.len));
    }
    c.res += d.count();
  }
  return c;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int d, m;
  cin >> d >> m;
vector<int> gen(d);
for (int i = 0; i < d; i++) {
    cin >> gen[i];
}
cin >> n;
vector<int> b(n);
for (int i = 0; i < n; i++) {
    cin >> b[i];
}
long long L, R;
cin >> L >> R;
for (int i = 1; i < n; i++) {
    all.set(i);
  }
  vector<vector<State>> states(1, vector<State>(m));
for (int i = 0; i < m; i++) {
    states[0][i].len = 1;
    if (n == 1) {
      states[0][i].res = b[0] >= i;
} else {
for (int j = 1; j < n; j++) {
        if (b[j] >= i) {
states[0][i].left.set(j);
}
}
for (int j = 1; j < n; j++) {
        if (b[j - 1] >= i) {
states[0][i].right.set(j);
}
}
}
}
long long z = 1;
while (z <= R / d) {
    int sz = (int) states.size();
    states.resize(sz + 1);
    states[sz].resize(m);
    for (int i = 0; i < m; i++) {
      State cur = states[sz - 1][i];
      for (int j = 1; j < d; j++) {
        cur = Unite(cur, states[sz - 1][(i + gen[j]) % m]);
      }
      states[sz][i] = cur;
    }
    z *= d;
  }
  auto calc = [&](long long up) -> long long {
State res;
int shift = 0;
for (int i = (int) states.size() - 1; i >= 0; i--) {
z = 1;
for (int j = 0; j < i; j++) {
        z *= d;
      }
      for (int j = 0; j < d; j++) {
        if (up >= z) {
res = Unite(res, states[i][(shift + gen[j]) % m]);
up -= z;
} else {
shift = (shift + gen[j]) % m;
break;
}
}
}
return res.res;
};
cout << calc(R) - calc(L + n - 2) << '\n';
  return 0;
}

New Year and the Treasure Geolocation

Uniqueness

The Child and Binary Tree

Running with Obstacles