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>
#pragma GCC target("pclmul")
using ul = std::uint32_t;
using ull = std::uint64_t;
using li = std::int32_t;
using ll = std::int64_t;
using llf = long double;
using uss = std::uint8_t;
using lll = __int128;
const ul maxd = 20;
const ul maxn = 30000;
const ul maxm = 60;
ul gen[maxd];
ul b[maxn + 1];
ull right[maxn + 1][61];
ull left[maxn + 1][61];
lll dpow[61];
ull cnt[61][maxd][maxm];
ul n, m, d;
ul plus(ul a, ul b) { return a + b < m ? a + b : a + b - m; }
ul minus(ul a, ul b) { return a < b ? a + m - b : a - b; }
ull move(ull x, ul g) { return (x >> g | x << m - g) & (ull(1) << m) - 1; }
ul calc(ull x) {
  ul ret = 0;
  while (x) {
    ret = plus(ret, gen[x % d]);
    x /= d;
  }
  return ret;
}
std::map<ull, ull> solved[61][maxm];
ull getans(ull r) {
  ull ret = 0;
  if (n == 1) {
    for (ul v = 0; v <= b[1]; ++v) {
      ull beta = r + 1;
      for (ul j = 0; beta; ++j, beta /= d) {
        ul q = beta % d;
        if (q != 0) {
          ret += cnt[j][q - 1][minus(v, calc((beta - 1) / d))];
        }
      }
    }
    return ret;
  }
  for (ul s = 1, t = 2; t <= n; ++s, ++t) {
    for (ul g = 1;; ++g) {
      if (dpow[g] < n) {
        continue;
      }
      if (dpow[g - 1] < s) {
        continue;
      }
      for (ul i = 1; i <= d - 1 && n - t + 1 <= (d - 1 - i + 1) * dpow[g - 1];
           ++i) {
        if (r < dpow[g - 1] * i + n - t) {
          break;
        }
        ull x = (ull(1) << m) - 1;
        x &= move(left[s][g - 1], gen[i - 1]);
        ull k = t;
        for (ul j = i; j <= d - 1 && k <= n; ++j, k += dpow[g - 1]) {
          x &= move(right[k][g - 1], gen[j]);
        }
        ull alpha = (r - n + t - dpow[g - 1] * i) / dpow[g];
        ++alpha;
        ul asum = calc(alpha);
        for (ul v = 0; v != m; ++v) {
          if (~x >> v & 1) {
            continue;
          }
          ul sum = asum;
          ull beta = alpha;
          auto it = solved[g][v].find(beta);
          if (it != solved[g][v].end()) {
            ret += it->second;
          } else {
            ull tmp = 0;
            for (ul j = 0; beta; ++j, beta /= d) {
              ul q = beta % d;
              sum = minus(sum, gen[q]);
              if (q != 0) {
                tmp += cnt[j][q - 1][minus(v, sum)];
              }
            }
            solved[g][v][alpha] = tmp;
            ret += tmp;
          }
        }
      }
      if (dpow[g] > r) {
        break;
      }
    }
  }
  return ret;
}
ull r, l;
int main() {
  std::scanf("%u%u", &d, &m);
  dpow[0] = 1;
  for (ul i = 1; i <= 60; ++i) {
    dpow[i] = dpow[i - 1] * d;
  }
  for (ul i = 0; i <= d - 1; ++i) {
    std::scanf("%u", &gen[i]);
  }
  for (ul g = 0; g <= 59; ++g) {
    for (ul i = 0; i <= d - 1; ++i) {
      if (i != 0) {
        std::memcpy(cnt[g][i], cnt[g][i - 1], sizeof(ull) * m);
      }
      if (g == 0) {
        ++cnt[g][i][gen[i]];
      } else {
        for (ul j = 0; j != m; ++j) {
          cnt[g][i][plus(j, gen[i])] += cnt[g - 1][d - 1][j];
        }
      }
    }
  }
  std::scanf("%u", &n);
  for (ul i = 1; i <= n; ++i) {
    std::scanf("%u", &b[i]);
    left[i][0] = (ull(1) << b[i] + 1) - 1;
    right[i][0] = (ull(1) << b[i] + 1) - 1;
  }
  for (ul i = n; i >= 1; --i) {
    for (ul q = 0, dq = 1; q <= 59; ++q) {
      right[i][q + 1] = (ull(1) << m) - 1;
      for (ul j = 0; j <= d - 1 && dq * j <= n - i; ++j) {
        right[i][q + 1] &= move(right[i + dq * j][q], gen[j]);
      }
      if (dq < n - i + 1) {
        dq *= d;
      }
    }
  }
  for (ul i = 1; i <= n; ++i) {
    for (ul q = 0, dq = 1; q <= 59; ++q) {
      left[i][q + 1] = (ull(1) << m) - 1;
      for (ul j = 0; j <= d - 1 && i - 1 >= dq * j; ++j) {
        left[i][q + 1] &= move(left[i - dq * j][q], gen[d - 1 - j]);
      }
      if (dq < i) {
        dq *= d;
      }
    }
  }
  std::scanf("%llu%llu", &l, &r);
  --r;
  --l;
  ull ans = getans(r);
  if (l != 0) {
    ans -= getans(l - 2 + n);
  }
  std::printf("%llu\n", ans);
  return 0;
}