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 cnt, len, n, m, pt, gen[209], p[209], b[30009];
long long l, r, ans, dp[209][209];
map<long long, int> mp;
int read() {
  int x = 0;
  char ch = getchar();
  bool flag = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return flag ? -x : x;
}
long long readll() {
  long long x = 0;
  char ch = getchar();
  bool flag = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return flag ? -x : x;
}
int calc(long long x) {
  if (mp[x]) return mp[x];
  mp[x] = ++pt;
  static int p[209];
  static long long f[209][209][2];
  int len = 0;
  for (; x; x /= cnt) p[++len] = x % cnt;
  memset(f, 0, sizeof(f));
  f[0][0][1] = 1;
  int i, j, k, l;
  for (i = 1; i <= len; i++)
    for (j = 0; j < m; j++)
      for (k = 0; k < 2; k++)
        for (l = 0; l <= (k ? cnt - 1 : p[i]); l++)
          f[i][(j + gen[l]) % m][k] += f[i - 1][j][k | (l < p[i])];
  for (i = 0; i < m; i++) dp[pt][i] = f[len][i][0];
  return pt;
}
void work(vector<long long> f, int k, bool flag) {
  int i;
  if (f.size() == 1) {
    if (f[0]) {
      long long tmp = 0;
      for (i = len; i >= k; i--) tmp = tmp * cnt + p[i];
      int now = calc(tmp + flag);
      for (i = 0; i < m; i++)
        if (f[0] >> i & 1) ans += dp[now][i];
    }
    return;
  }
  if (k > len && !flag) return;
  vector<long long> g;
  for (i = 0; i < cnt; i++) {
    g.clear();
    int j = i;
    long long now = (1ll << m) - 1;
    for (long long x : f) {
      long long y = x >> gen[j] | (x & (1ll << gen[j]) - 1) << m - gen[j];
      if (!j)
        now = y;
      else
        now &= y;
      j = (j + 1) % cnt;
      if (!j) {
        g.push_back(now);
        now = -1;
      }
    }
    if (now != -1) g.push_back(now);
    work(g, k + 1, i == p[k] ? flag : i < p[k]);
  }
}
void solve(long long t) {
  int i;
  len = 0;
  for (; t; t /= cnt) p[++len] = t % cnt;
  vector<long long> f;
  f.clear();
  for (i = 1; i <= n; i++) f.push_back((1ll << b[i] + 1) - 1);
  work(f, 1, 0);
}
int main() {
  scanf("%d%d", &cnt, &m);
  int i;
  for (i = 0; i < cnt; i++) scanf("%d", &gen[i]);
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &b[i]);
  scanf("%lld%lld", &l, &r);
  r -= n - 1;
  if (l > r) {
    puts("0");
    return 0;
  }
  long long t = 0;
  solve(r);
  t += ans;
  ans = 0;
  solve(l - 1);
  t -= ans;
  printf("%lld\n", t);
  return 0;
}