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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define make(A) scanf("%d",&A)
#define make2(A,B) scanf("%d%d",&A,&B)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define db if(1)printf
template<typename C> void MA(C& a,C b){if(a<b)a=b;}
template<typename C> void MI(C& a,C b){if(a>b)a=b;}
#define MAX 1001000
const LL inf = 2e18;
int t[MAX],p[MAX],kie[MAX];
int n,m;
char z[MAX];
vector<int> dd[MAX*2 + 100];
vector<int>* d = dd + MAX + 50;
int spr(int war,int kt){
  if(war > MAX || war < -MAX)return -1;
  auto pom = lower_bound(ALL(d[war]),kt);
  if(pom == d[war].end())
    return -1;
  return *pom;
}
LL wyn[MAX];
main(){
  make(n);
  R(i,n)make(t[i]);
  make(m);
  scanf("%s",z);
  int krok = n%m;
  int nc = __gcd(n,m);
  R(i,nc){
    int sum = 0;
    int gd = i;
    int kt = 0;
    int mi = 1;
    do{
      p[kt] = sum;
      kie[gd] = kt;
      sum += z[gd] == 'W'?1:-1; 
      MI(mi,sum);
      d[sum].PB(kt);
      kt++;
      gd += krok;
      if(gd >= m)gd -= m;
    }while(i!=gd);
    for(int j = i; j < n;j+=nc){
      int st = kie[j%m];
      int szu = t[j] - p[st];
      int res = spr(-szu,st);
      if(res != -1){
        wyn[j] =  (res - st) * 1ll * n + j;
        continue;
      }
      szu += sum;
      if(szu + mi <= 0){
        wyn[j] = (*d[-szu].begin() + kt - st) * 1ll * n + j;
      }else
      if(sum < 0){
        int obr = (szu + mi - sum - 1) / -sum;
        szu += obr * sum;
        wyn[j] = (*d[-szu].begin() + kt - st + obr *1ll* kt)*n + j;
      }else
        wyn[j] = inf;
    }
    while(SZ(d[mi])){
      d[mi].clear();
      mi++;
    }
  }
  LL wynik = *min_element(wyn,wyn+n);
  if(wynik == inf)
    puts("-1");
  else
    printf("%lld\n",wynik+1);
//   R(i,n){
//     if(wyn[i] == inf || wyn[i] > 10000000)
//       puts("-1");
//     else
//       printf("%lld\n",wyn[i]+1);
//   }
}