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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
static int d, m;
static vector<int> gen;
static vector<int> prefix;
static int sub(int x, int y) {
  x -= y;
  if (x < 0) x += m;
  return x;
}
struct interval {
  long long mask = 0;
  explicit interval(long long mask = 0) : mask(mask) {}
  interval operator&(const interval &x) const {
    return interval(mask & x.mask);
  }
  interval operator-(int shift) const {
    long long smask = (1LL << shift) - 1;
    return interval((mask >> shift) | ((mask & smask) << (m - shift)));
  }
  bool contains(int v) const { return mask & (1LL << v); }
};
static interval all;
static unordered_map<long long, vector<long long> > memo;
static vector<long long> &prepare(long long R) {
  auto pos = memo.find(R);
  if (pos == memo.end()) {
    vector<long long> &ans = memo[R];
    ans.resize(m);
    if (R <= d) {
      for (long long i = 0; i < R; i++) ans[gen[i]]++;
    } else {
      for (int p = 0; p < d; p++) {
        long long R1 = (R - p + d - 1) / d;
        const auto &ch = prepare(R1);
        for (int i = 0; i < m; i++) ans[i] += ch[sub(i, gen[p])];
      }
    }
    return ans;
  } else
    return pos->second;
}
static inline long long solve0(int v, long long R) { return prepare(R)[v]; }
static long long solve1(const interval &b, long long R) {
  long long ans = 0;
  for (int i = 0; i < m; i++)
    if (b.contains(i)) ans += solve0(i, R);
  return ans;
}
static long long solve(const vector<interval> &b, long long R) {
  int N = ((long long)(b).size());
  long long ans = 0;
  if (R <= d && N <= d) {
    for (int i = 0; i < R; i++) {
      bool good = true;
      for (int j = 0; j < N; j++)
        if (!b[j].contains(prefix[i + j])) good = false;
      ans += good;
    }
    return ans;
  } else if (N > 1) {
    for (int p = 0; p < d; p++) {
      int No = (N + p + d - 1) / d;
      vector<interval> c(No);
      int ofs = -p;
      for (int i = 0; i < No; i++) {
        interval cur = all;
        for (int j = 0; j < d; j++, ofs++) {
          if (ofs >= 0 && ofs < N) cur = cur & (b[ofs] - gen[j]);
        }
        c[i] = cur;
      }
      ans += solve(c, (R - p + d - 1) / d);
    }
    return ans;
  } else
    return solve1(b[0], R);
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  cin >> d >> m;
  all = interval((1LL << m) - 1);
  gen.resize(d);
  for (int i = 0; i < d; i++) cin >> gen[i];
  prefix = gen;
  for (int i = 0; i < d; i++) prefix.push_back((gen[i] + gen[1]) % m);
  int N;
  cin >> N;
  vector<interval> b(N);
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    b[i] = interval((2LL << x) - 1);
  }
  long long L, R;
  cin >> L >> R;
  L--;
  R--;
  cout << solve(b, R - N + 2) - solve(b, L) << '\n';
  return 0;
}