Problem: A Thue-Morse-Radecki-Mateusz sequence (Thorse-Radewoosh sequence in short) is an infinite sequence constructed from a finite sequence 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 ≥ 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 ≤ i ≤ d), each element x is changed to (x+gen_i) \pmod{m}. 



For instance, if we pick 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 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_∞ as the sequence obtained by applying the step above indefinitely. For the parameters above, M_∞ = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, ...).

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

Note that we use the 1-based indexing both for M_∞ 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 ≥ X) if and only if for all i ∈ \{1, 2, ..., n\}, we have B_i ≥ X_i.

He now asks himself how many integers x in the range [1, |A| - n + 1] there are such that B ≥ (A_x, A_{x+1}, A_{x+2}, ..., 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 ≤ d ≤ 20, 2 ≤ m ≤ 60) — the length of the sequence gen and an integer used to perform the modular operations. The second line contains d integers gen_i (0 ≤ gen_i < m). It's guaranteed that the first element of the sequence gen is equal to zero.

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

Output

Print a single integer — the answer to the problem.

Examples

Input


2 2
0 1
4
0 1 1 0
2 21


Output


6


Input


3 4
0 1 2
2
0 2
6 11


Output


1

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:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int mod;
struct Sum2D {
  int n, m;
  long long** pref;
  Sum2D(){};
  Sum2D(long long** a) : n(mod), m(mod) {
    pref = new long long*[n + 1];
    for (int i = 0; i <= n; ++i) {
      pref[i] = new long long[m + 1];
      for (int x = 0; x < mod; ++x) pref[i][x] = 0;
    }
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        pref[i + 1][j + 1] =
            a[i][j] + pref[i + 1][j] + pref[i][j + 1] - pref[i][j];
  }
  long long get_sum(int lx, int rx, int ly, int ry) {
    ++rx;
    ++ry;
    return pref[rx][ry] - pref[rx][ly] - pref[lx][ry] + pref[lx][ly];
  }
};
int mlog(long long r, long long d) {
  int k = 0;
  for (long long pw = 1; pw <= r / d; ++k) pw *= d;
  return k;
}
long long mpow(long long x, int k) {
  long long res = 1;
  while (k--) res *= x;
  return res;
}
int a[66];
vector<pair<int, int>> split_segment(long long mask) {
  int n = mod;
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    a[i] = (mask >> i) & 1;
    cnt += a[i];
  }
  if (cnt == 0) return {};
  if (cnt == n) return {{0, n - 1}};
  vector<pair<int, int>> res;
  for (int i = 0; i < n; ++i) {
    int l = i;
    while (l < n && !a[l]) ++l;
    if (l == n) break;
    int r = l;
    while (r < n && a[r]) ++r;
    res.push_back({l, r - 1});
    i = r;
  }
  return res;
}
const int D = 20;
const int MOD = 60;
const int N = 30000;
const int LOG = 16;
using Zet = long long*;
int d;
int logn;
int gen[D];
vector<int> big_gen;
long long pwd[66];
long long jump[N][LOG];
pair<vector<pair<int, int>>, vector<pair<int, int>>> segments[N * D];
void add(Zet arr, Zet to_add, int shift) {
  for (int i = 0; i + shift < mod; ++i) arr[i] += to_add[i + shift];
  for (int i = mod - shift; i < mod; ++i) arr[i] += to_add[i + shift - mod];
}
Zet zeroes;
unordered_map<long long, Zet> cnt;
Zet get_cnt(long long r) {
  if (r <= 0) return zeroes;
  if (cnt.count(r)) return cnt[r];
  Zet res = new long long[mod];
  for (int x = 0; x < mod; ++x) res[x] = 0;
  int k = mlog(r, d);
  long long dk = mpow(d, k);
  if (dk == r) dk /= d;
  int i = 0;
  for (; r >= (i + 1) * dk; ++i) add(res, get_cnt(dk), (mod - gen[i]) % mod);
  add(res, get_cnt(r - i * dk), (mod - gen[i % d]) % mod);
  cnt[r] = res;
  return res;
};
void inters(long long& mask1, long long mask2, int shift) {
  long long shift_mask = mask2 & ((1LL << shift) - 1);
  mask1 &= ((mask2 >> shift) | (shift_mask << (mod - shift)));
}
long long query(int l, int r, int pos) {
  long long res = (1LL << mod) - 1;
  while (l != r) {
    for (int i = logn;; --i) {
      if (l % pwd[i] == 0 && l + pwd[i] <= r) {
        inters(res, jump[pos][i], big_gen[l]);
        l += pwd[i];
        pos += pwd[i];
        break;
      }
    }
  }
  return res;
};
unordered_map<long long, Sum2D> solver;
long long get_sum(long long R, int lx, int rx, int ly, int ry) {
  if (!solver.count(R)) {
    Zet* a = new Zet[mod];
    for (int i = 0; i < mod; ++i) {
      a[i] = new long long[mod];
      for (int x = 0; x < mod; ++x) a[i][x] = 0;
    }
    for (int i = 0; pwd[i] - 1 <= R; ++i) {
      for (int digit = 0; digit < d - 1; ++digit) {
        if (R < (digit + 1) * pwd[i] - 1) break;
        Zet kek = get_cnt((R - (digit + 1) * pwd[i] + 1) / pwd[i + 1] + 1);
        for (int r = 0; r < mod; ++r)
          a[(r + gen[digit] + i * gen[d - 1]) % mod]
           [(r + gen[digit + 1]) % mod] += kek[r];
      }
    }
    solver[R] = Sum2D(a);
  }
  return solver[R].get_sum(lx, rx, ly, ry);
};
long long solve(long long R) {
  long long res = 0;
  for (int rem = 0; rem < pwd[logn] && rem <= R; ++rem) {
    vector<pair<int, int>>& v1 = segments[rem].first;
    vector<pair<int, int>>& v2 = segments[rem].second;
    for (auto& [lx, rx] : v1)
      for (auto& [ly, ry] : v2)
        res += get_sum((R - rem) / pwd[logn], lx, rx, ly, ry);
  }
  return res;
};
int main() {
  scanf("%d %d", &d, &mod);
  for (int i = 0; i < d; ++i) scanf("%d", &gen[i]);
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  logn = 1;
  for (int i = 0; i < d; ++i) big_gen.push_back(gen[i]);
  for (; (int)(big_gen).size() < n; ++logn) {
    vector<int> new_big_gen;
    for (int i = 0; i < d; ++i) {
      for (int x : big_gen) new_big_gen.push_back((x + gen[i]) % mod);
    }
    big_gen = new_big_gen;
  }
  int pos = 0;
  pwd[pos] = 1;
  while (pwd[pos] < (long long)4e17) {
    long long x = d * pwd[pos];
    pwd[++pos] = x;
  }
  for (int i = n - 1; i >= 0; --i) {
    jump[i][0] = (1LL << (a[i] + 1)) - 1;
    for (int k = 1; i + pwd[k] <= n; ++k) {
      jump[i][k] = (1LL << mod) - 1;
      for (int ii = 0; ii < d; ++ii) {
        inters(jump[i][k], jump[i + ii * pwd[k - 1]][k - 1], gen[ii]);
      }
    }
  }
  for (int rem = 0; rem <= pwd[logn] - n; ++rem) {
    long long draw = query(rem, rem + n, 0);
    segments[rem] = {split_segment(draw), {{0, mod - 1}}};
  }
  for (int rem = pwd[logn] - n + 1; rem < pwd[logn]; ++rem) {
    long long draw1 = query(rem, pwd[logn], 0);
    long long draw2 = query(0, n - (pwd[logn] - rem), pwd[logn] - rem);
    segments[rem] = {split_segment(draw1), split_segment(draw2)};
  }
  zeroes = new long long[mod];
  for (int x = 0; x < mod; ++x) zeroes[x] = 0;
  cnt[0] = zeroes;
  Zet ozero = new long long[mod];
  for (int x = 0; x < mod; ++x) ozero[x] = 0;
  ozero[0] = 1;
  cnt[1] = ozero;
  long long l, r;
  scanf("%lld %lld", &l, &r);
  --l;
  --r;
  printf("%lld\n", solve(r - n + 1) - solve(l - 1));
}