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;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 30011;
bitset<maxn> all1;
int n, m, b[maxn];
struct data {
  bitset<maxn> pf[61], sf[61];
  int dlt;
  int gi(int x) const { return (x + dlt) % m; }
  long long len, ans[61];
  data shift(int d) {
    data ret = (*this);
    ret.dlt = (ret.dlt + d) % m;
    return ret;
  }
  void init1() {
    len = 1;
    dlt = 0;
    for (int i = 0; i < m; i++) {
      pf[i].reset();
      for (int j = 0; j < n; j++) pf[i][j] = b[j] >= i;
      sf[i].reset();
      sf[i][0] = 1;
      for (int j = 0; j < n - 1; j++) sf[i][j + 1] = b[j] >= i;
      ans[i] = n == 1 && b[0] >= i;
    }
  }
  void debug() {
    if (0) cout << "===debug===" << endl;
    if (0)
      cout << "len = " << len << " dlt = " << dlt << " ans = " << ans[0]
           << endl;
    for (int t = 0; t < m; t++) {
      for (int i = 0; i < n; i++)
        if (0) cout << pf[t][i];
      if (0) cout << ",";
    }
    if (0) cout << endl;
    for (int t = 0; t < m; t++) {
      for (int i = 0; i < n; i++)
        if (0) cout << sf[t][i];
      if (0) cout << ",";
    }
    if (0) cout << endl;
  }
};
data merge(const data &l, const data &r) {
  data ret;
  ret.len = l.len + r.len;
  ret.dlt = 0;
  for (int i = 0; i < m; i++) {
    ret.pf[i] = l.pf[l.gi(i)];
    if (l.len < n) ret.pf[i] &= r.pf[r.gi(i)] >> l.len | all1 << (n - l.len);
    ret.sf[i] = r.sf[r.gi(i)];
    if (r.len < n) ret.sf[i] &= l.sf[l.gi(i)] << r.len | all1 >> (maxn - r.len);
    ret.ans[i] = l.ans[l.gi(i)] + r.ans[r.gi(i)];
    int tmp = min(l.len, (long long)n - 1);
    int tmpl = max(1ll, n - r.len);
    if (tmp >= tmpl) {
      ret.ans[i] += (((l.sf[l.gi(i)] & (r.pf[r.gi(i)])) >> tmpl)
                     << (maxn - tmp + tmpl - 1))
                        .count();
    }
  }
  return ret;
}
int K;
data A[66];
int d, gen[66];
data solve(long long N) {
  assert(N > 0);
  for (int i = K; i >= 0; i--) {
    if (N == A[i].len) return A[i];
    if (N > A[i].len) {
      data ret = A[i];
      for (int j = 1; j < d; j++) {
        if (N > A[i].len * (j + 1))
          ret = merge(ret, A[i].shift(gen[j]));
        else {
          ret = merge(ret, solve(N - A[i].len * j).shift(gen[j]));
          return ret;
        }
      }
      assert(false);
    }
  }
}
long long calc(long long N) {
  if (N <= 0) return 0;
  data cur = solve(N);
  return cur.ans[cur.gi(0)];
}
int main() {
  all1.set();
  d = getnum(), m = getnum();
  for (int i = 0; i < d; i++) gen[i] = getnum();
  n = getnum();
  for (int i = 0; i < n; i++) b[i] = getnum();
  A[0].init1();
  while (true) {
    K++;
    A[K] = A[K - 1];
    bool exceed = 0;
    for (int i = 1; i < d; i++) {
      A[K] = merge(A[K], A[K - 1].shift(gen[i]));
      if (A[K].len > 2e18) {
        exceed = 1;
        break;
      }
    }
    if (exceed) {
      K--;
      break;
    }
  }
  long long l, r;
  l = getnum(), r = getnum();
  cout << calc(r) - calc(l + n - 2) << endl;
  return 0;
}