1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

struct FastIO {
  static const int S = 2310720;
  inline int xchar() {
    static char buf[S];
    static int len = 0, pos = 0;
    if (pos == len)
      pos = 0, len = fread(buf, 1, S, stdin);
    if (pos == len) return -1;
    return buf[pos ++];
  }
  inline int xint() {
    int c = xchar(), x = 0;
    while (c <= 32) c = xchar();
    for (;'0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
    return x;
  }
  inline void xstring(char *s) {
    int c = xchar();
    while (c <= 32) c = xchar();
    for(; c > 32; c = xchar()) *s++ = c;
    *s = 0;
  }
} io;

const int MAXN = 1000000 + 10, SIZE = MAXN << 1;
char s[MAXN];
int id[SIZE], q[SIZE], r[SIZE];
int a[MAXN], n, m;

inline void upd(LL &x, LL y) {
  if (x == -1 || x > y) x = y;
}

int find(int l, int r, int v) {
  while (l < r) {
    int m = (l + r - 1) >> 1;
    if (::r[q[m]] >= v) r = m;
    else l = m + 1;
  }
  assert(::r[q[l]] == v);
  return l;
}

int main() {
  n = io.xint();
  for (int i = 0; i < n; ++ i) a[i] = io.xint();
  m = io.xint(); io.xstring(s);
  LL ret(-1);
  for (int i = 0; i < m; ++ i) if (s[i]) {
    int sz(0);
    for (int j = i; s[j]; j = (j + n) % m) {
      id[++ sz] = j;
      r[sz] = s[j] == 'W' ? 1 : -1;
      s[j] = 0;
    }
    for (int j = 1; j <= sz; ++ j) r[j + sz] = r[j];
    for (int j = 1; j <= sz * 2; ++ j) r[j] += r[j - 1];
    int h(1), t(0), sum(r[sz]);
    for (int j = sz; j >= 1; -- j) {
      while (h <= t && r[q[t]] >= r[j + sz]) -- t;
      q[++ t] = j + sz;
    }
    for (int j = sz; j >= 1; -- j) {
      while (h <= t && q[h] >= j + sz) ++ h;
      while (h <= t && r[q[t]] >= r[j]) -- t;
      q[++ t] = j; if (!a[id[j]]) continue;
      for (int k = id[j]; k < n; k += m) {
        if (r[q[h]] - r[j - 1] + a[k] <= 0) {
          int v = r[j - 1] - a[k];
          v = find(h, t, v); v = q[v];
          upd(ret, k + LL(v - j) * n + 1);
        }
        else if (sum < 0) {
          LL u = (r[j - 1] - a[k] - r[q[h]]) / sum;
          a[k] += u * sum;
          while (a[k] + r[q[h]] - r[j - 1] > 0) ++ u, a[k] += sum;
          assert(a[k] > 0);
          int v = r[j - 1] - a[k];
          v = find(h, t, v); v = q[v];
          upd(ret, k + LL(v - j) * n + u * n * sz + 1);
        }
        a[k] = 0;
      }
    }
  }
  printf("%lld\n", ret);
  return 0;
}